cssi/SciSciGPT-SciSciNet huggingface dataset:
Device-aware routing and scheduling in multi-hop Device-to-Device networks

The dramatic increase in data and connectivity demand, in addition to heterogeneous device capabilities, poses a challenge for future wireless networks. One of the promising solutions is Device-to-Device (D2D) networking. D2D networking, advocating the idea of connecting two or more devices directly without traversing the core network, is promising to address the increasing data and connectivity demand. In this paper, we consider D2D networks, where devices with heterogeneous capabilities including computing power, energy limitations, and incentives participate in D2D activities heterogeneously. We develop (i) a device-aware routing and scheduling algorithm (DARS) by taking into account device capabilities, and (ii) a multi-hop D2D testbed using Android-based smartphones and tablets by exploiting Wi-Fi Direct and legacy Wi-Fi connections. We show that DARS significantly improves throughput in our testbed as compared to state-of-the-art.
Height Zeta Functions of Equivariant Compactifications of Unipotent Groups

We prove Manin's conjecture for bi-equivariant compactifications of unipotent groups. © 2015 Wiley Periodicals, Inc.
Characterizing Sparse Graphs by Map Decompositions

A map is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into k edge-disjoint maps after: (1) the addition of any ‘ edges; (2) the addition of some ‘ edges. These graphs are identied with classes of sparse graphs; the results are also given in matroidal terms.
Invariant Measures and the Soliton Resolution Conjecture

The soliton resolution conjecture for the focusing nonlinear Schrodinger equation (NLS) is the vaguely worded claim that a global solution of the NLS, for generic initial data, will eventually resolve into a radiation component that disperses like a linear solution, plus a localized component that behaves like a soliton or multisoliton solution. Considered to be one of the fundamental open problems in the area of nonlinear dispersive equations, this conjecture has eluded a proof or even a precise formulation to date. This paper proves a “statistical version” of this conjecture at mass-subcritical nonlinearity, in the following sense: The uniform probability distribution on the set of all functions with a given mass and energy, if such a thing existed, would be a natural invariant measure for the NLS flow and would reflect the long-term behavior for “generic initial data” with that mass and energy. Unfortunately, such a probability measure does not exist. We circumvent this problem by constructing a sequence of discrete measures that, in principle, approximate this fictitious probability distribution as the grid size goes to 0. We then show that a continuum limit of this sequence of probability measures does exist in a certain sense, and in agreement with the soliton resolution conjecture, the limit measure concentrates on the unique ground state soliton. Combining this with results from ergodic theory, we present a tentative formulation and proof of the soliton resolution conjecture in the discrete setting. The above results, following in the footsteps of a program of studying the long-term behavior of nonlinear dispersive equations through their natural invariant measures initiated by Lebowitz, Rose, and Speer and carried forward by Bourgain, McKean, Tzvetkov, Oh, and others, are proved using a combination of techniques from large deviations, PDEs, harmonic analysis, and bare-hands probability theory. It is valid in any dimension. © 2014 Wiley Periodicals, Inc.
Scaling Principles of Distributed Circuits.

Summary Identifying shared quantitative features of a neural circuit across species is important for 3 reasons. Often expressed in the form of power laws and called scaling relationships [ 1 , 2 ], they reveal organizational principles of circuits, make insights gleaned from model systems widely applicable, and explain circuit performance and function, e.g., visual circuits [ 3 , 4 ]. The visual circuit is topographic [ 5 , 6 ], wherein retinal neurons target and activate predictable spatial loci in primary visual cortex. The brain, however, contains many circuits, where neuronal targets and activity are unpredictable and distributed throughout the circuit, e.g., olfactory circuits, in which glomeruli (or mitral cells) in the olfactory bulb synapse with neurons distributed throughout the piriform cortex [ 7 , 8 , 9 , 10 ]. It is unknown whether such circuits, which we term distributed circuits, are scalable. To determine whether distributed circuits scale, we obtained quantitative descriptions of the olfactory bulb and piriform cortex in six mammals using stereology techniques and light microscopy. Two conserved features provide evidence of scalability. First, the number of piriform neurons n and bulb glomeruli g scale as n ∼ g 3 / 2 . Second, the average number of synapses between a bulb glomerulus and piriform neuron is invariant at one. Using theory and modeling, we show that these two features preserve the discriminatory ability and precision of odor information across the olfactory circuit. As both abilities depend on circuit size, manipulating size provides evolution with a way to adapt a species to its niche without designing developmental programs de novo . These principles might apply to other distributed circuits like the hippocampus.
Three-dimensional segmentation of vesicular networks of fungal hyphae in macroscopic microscopy image stacks

Automating the extraction and quantification of features from three-dimensional (3-D) image stacks is a critical task for advancing many applications, such as the analysis of biological structures. The quantification of biological resistance of a plant tissue to fungal infection through the analysis of attributes such as fungal penetration depth, fungal mass, and branching of the fungal network at large scales requires the union of 3D image acquisition and analysis. From an image processing perspective, these tasks reduce to segmentation of vessel-like structures and the extraction of features from their skeletonization. In order to sample multiple infection events for analysis, we have developed an approach we refer to as macroscopic microscopy. However, macroscopic microscopy produces high-resolution image stacks that pose challenges to routine approaches and are difficult for a human to annotate to obtain ground truth data. We present a synthetic hyphal network generator, a comparison of several vessel segmentation methods, and a minimum spanning tree method for connecting small gaps resulting from imperfections in imaging or incomplete skeletonization of hyphal networks. Qualitative results are shown for real microscopic data. We believe the comparison of vessel detectors on macroscopic microscopy data, the synthetic vessel generator, and the gap closing technique are beneficial to the image processing community.
Spin-bath narrowing with adaptive parameter estimation

We present a measurement scheme capable of achieving the quantum limit of parameter estimation using an adaptive strategy that minimizes the parameter's variance at each step. The adaptive rule we propose makes the scheme robust against errors, in particular imperfect readouts, a critical requirement to extend adaptive schemes from quantum optics to solid-state sensors. Thanks to recent advances in single-shot readout capabilities for electronic spins in the solid state (such as nitrogen vacancy centers in diamond), this scheme can also be applied to estimate the polarization of a spin bath coupled to the sensor spin. In turns, the measurement process decreases the entropy of the spin bath resulting in longer coherence times of the sensor spin.
SqueezeSeg: Convolutional Neural Nets with Recurrent CRF for Real-Time Road-Object Segmentation from 3D LiDAR Point Cloud

We address semantic segmentation of road-objects from 3D LiDAR point clouds. In particular, we wish to detect and categorize instances of interest, such as cars, pedestrians and cyclists. We formulate this problem as a point-wise classification problem, and propose an end-to-end pipeline called SqueezeSeg based on convolutional neural networks (CNN): the CNN takes a transformed LiDAR point cloud as input and directly outputs a point-wise label map, which is then refined by a conditional random field (CRF) implemented as a recurrent layer. Instance-level labels are then obtained by conventional clustering algorithms. Our CNN model is trained on LiDAR point clouds from the KITTI [1] dataset, and our point-wise segmentation labels are derived from 3D bounding boxes from KITTI. To obtain extra training data, we built a LiDAR simulator into Grand Theft Auto $\boldsymbol{V}$ (GTA-V), a popular video game, to synthesize large amounts of realistic training data. Our experiments show that SqueezeSeg achieves high accuracy with astonishingly fast and stable runtime ($8.7\pm 0.5$ ms per frame), highly desirable for autonomous driving. Furthermore, additionally training on synthesized data boosts validation accuracy on real-world data. Our source code is open-source released111https://github.com/BichenWuUCB/SqueezeSeg. The paper is accompanied by a video222https://youtu.be/Xyn5Zd31m6s containing a high level introduction and demonstrations of this work.
Heterogeneous Supervision for Relation Extraction: A Representation Learning Approach

Relation extraction is a fundamental task in information extraction. Most existing methods have heavy reliance on annotations labeled by human experts, which are costly and time-consuming. To overcome this drawback, we propose a novel framework, REHession, to conduct relation extractor learning using annotations from heterogeneous information source, e.g., knowledge base and domain heuristics. These annotations, referred as heterogeneous supervision, often conflict with each other, which brings a new challenge to the original relation extraction task: how to infer the true label from noisy labels for a given instance. Identifying context information as the backbone of both relation extraction and true label discovery, we adopt embedding techniques to learn the distributed representations of context, which bridges all components with mutual enhancement in an iterative fashion. Extensive experimental results demonstrate the superiority of REHession over the state-of-the-art.
Projective Dimension of String and Cycle Hypergraphs

We present a closed formula and a simple algorithmic procedure to compute the projective dimension of square-free monomial ideals associated to string or cycle hypergraphs. As an application, among these ideals we characterize all the Cohen–Macaulay ones.
Turbo Learning for CaptionBot and DrawingBot

We study in this paper the problems of both image captioning and text-to-image generation, and present a novel turbo learning approach to jointly training an image-to-text generator (a.k.a. CaptionBot) and a text-to-image generator (a.k.a. DrawingBot). The key idea behind the joint training is that image-to-text generation and text-to-image generation as dual problems can form a closed loop to provide informative feedback to each other. Based on such feedback, we introduce a new loss metric by comparing the original input with the output produced by the closed loop. In addition to the old loss metrics used in CaptionBot and DrawingBot, this extra loss metric makes the jointly trained CaptionBot and DrawingBot better than the separately trained CaptionBot and DrawingBot. Furthermore, the turbo-learning approach enables semi-supervised learning since the closed loop can provide peudo-labels for unlabeled samples. Experimental results on the COCO dataset demonstrate that the proposed turbo learning can significantly improve the performance of both CaptionBot and DrawingBot by a large margin.
Cuntz–Pimsner algebras, crossed products, and K-theory

Abstract Suppose A is a C ⁎ -algebra and H is a C ⁎ -correspondence over A . If H is regular in the sense that the left action of A is faithful and is given by compact operators, then we compute the K -theory of O A ( H ) ⋊ T where the action is the usual gauge action. The case where A is an AF-algebra is carefully analyzed. In particular, if A is AF, we show O A ( H ) ⋊ T is AF. Combining this with Takai duality and an AF-embedding theorem of N. Brown, we show the conditions AF-embeddability, quasidiagonality, and stable finiteness are equivalent for O A ( H ) . If H is also assumed to be regular, these finiteness conditions can be characterized in terms of the ordered K -theory of A .
An $L^1$ Ergodic Theorem for Sparse Random Subsequences

We prove an L^1 subsequence ergodic theorem for sequences chosen by independent random selector variables, thereby showing the existence of universally L^1-good sequences nearly as sparse as the set of squares. In the process, we prove that a certain deterministic condition implies a weak maximal inequality for a sequence of \ell^1 convolution operators.
The generalized fermion-bag approach

We present a new approach to some four-fermion lattice field t heories which we call the generalized fermion bag approach. The basic idea is to identify unpaired fermionic degrees of freedom that cause sign problems and collect them in a bag. Paired fermions usually act like bosons and do not lead to sign problems. A resummation of all unpaired fermion degrees of freedom inside the bag is sufficient to solve the fermion sign problem in a var iety of interesting cases. Using a concept of duality we then argue that the size of the fermion bags is small both at strong and weak couplings. This allows us to construct efficient algorithms in both these limits. Using the fermion bag approach, we study the quantum phase transition of the 3D massless lattice Thirrring model which is of interest in the context of Graphene. Using our method we are able to solve the model on lattices as large as 40 3 with moderate computational resources. We obtain the precise location of the quantum critical point and the values of the critical e xponents through this study.
Hamiltonian Monte Carlo Without Detailed Balance

We present a method for performing Hamiltonian Monte Carlo that largely eliminates sample rejection. In situations that would normally lead to rejection, instead a longer trajectory is computed until a new state is reached that can be accepted. This is achieved using Markov chain transitions that satisfy the fixed point equation, but do not satisfy detailed balance. The resulting algorithm significantly suppresses the random walk behavior and wasted function evaluations that are typically the consequence of update rejection. We demonstrate a greater than factor of two improvement in mixing time on three test problems. We release the source code as Python and MATLAB packages.
Geometric representations of graded and rational Cherednik algebras

Abstract We provide geometric constructions of modules over the graded Cherednik algebra H ν gr and the rational Cherednik algebra H ν rat attached to a simple algebraic group G together with a pinned automorphism θ. These modules are realized on the cohomology of affine Springer fibers (of finite type) that admit C ⁎ -actions. In the rational Cherednik algebra case, the standard grading on these modules is derived from the perverse filtration on the cohomology of affine Springer fibers coming from its global analog: Hitchin fibers. When θ is trivial, we show that our construction gives the irreducible finite-dimensional spherical modules L ν ( triv ) of H ν gr and of H ν rat . We give a formula for the dimension of L ν ( triv ) and give a geometric interpretation of its Frobenius algebra structure. The rank two cases are studied in further details.
Nonuniform thickness and weighted distance

Abstract Nonuniform tubular neighborhoods of curves in R n are studied by using weighted distance functions and generalizing the normal exponential map. Different notions of injectivity radii are introduced to investigate singular but injective exponential maps. A generalization of the thickness formula is obtained for nonuniform thickness. All singularities within almost injectivity radius are classified by the Horizontal Collapsing Property. Examples are provided to show the distinction between the different types of injectivity radii, as well as showing that the standard differentiable injectivity radius fails to be upper semicontinuous on a singular set of weight functions.
Model transition under local theta correspondence

Abstract We study model transition for representations occurring in the local theta correspondence between split even special orthogonal groups and symplectic groups, over a non-archimedean local field of characteristic zero.
Sparse linear regression via generalized orthogonal least-squares

The Orthogonal Least Squares (OLS) algorithm sequentially selects columns of the coefficient matrix to greedily find an approximate sparse solution to an underdetermined system of linear equations. In this paper, conditions under which OLS recovers sparse signals from a low number of random linear measurements with probability arbitrarily close to one are stated. Moreover, a computationally efficient generalization of Orthogonal Least-Squares which relies on a recursive relation between the components of the optimal solution to select L columns at each step and solve the resulting overdetermined system of equations is proposed. This generalized OLS algorithm is empirically shown to outperform existing greedy algorithms broadly used in literature.
A General Framework for Relational Parametricity

Reynolds' original theory of relational parametricity was intended to capture the observation that polymorphically typed System F programs preserve all relations between inputs. But as Reynolds himself later showed, his theory can only be formulated in a metatheory with an impredicative universe, such as the Calculus of Inductive Constructions. A number of more abstract treatments of relational parametricity have since appeared; however, as we show, none of these seem to express Reynolds' original theory in a satisfactory way.To correct this, we develop an abstract framework for relational parametricity that delivers a model expressing Reynolds' theory in a direct and natural way. This framework is uniform with respect to a choice of meta-theory, which allows us to obtain the well-known PER model of Longo and Moggi as a direct instance in a natural way as well. Underlying the framework is the novel notion of a λ2-fibration with isomorphisms, which relaxes certain strictness requirements on split λ2-fibrations. Our main theorem is a generalization of Seely's classical construction of sound models of System F from split λ2-fibrations: we prove that the canonical interpretation of System F induced by every λ2-fibration with isomorphisms validates System F's entire equational theory on the nose, independently of the parameterizing meta-theory.Moreover, we offer a novel relationally parametric model of System F (after Orsanigo), which is proof-relevant in the sense that witnesses of relatedness are themselves suitably related. We show that, unlike previous frameworks for parametricity, ours recognizes this new model in a natural way. Our framework is thus descriptive, in that it accounts for well-known models, as well as prescriptive, in that it identifies abstract properties that good models of relational parametricity should satisfy and suggests new constructions of such models.
Local minimax complexity of stochastic convex optimization

We extend the traditional worst-case, minimax analysis of stochastic convex optimization by introducing a localized form of minimax complexity for individual functions. Our main result gives function-specific lower and upper bounds on the number of stochastic subgradient evaluations needed to optimize either the function or its "hardest local alternative" to a given numerical precision. The bounds are expressed in terms of a localized and computational analogue of the modulus of continuity that is central to statistical minimax analysis. We show how the computational modulus of continuity can be explicitly calculated in concrete cases, and relates to the curvature of the function at the optimum. We also prove a superefficiency result that demonstrates it is a meaningful benchmark, acting as a computational analogue of the Fisher information in statistical estimation. The nature and practical implications of the results are demonstrated in simulations.
Codes for DNA storage channels

We consider the problem of assembling a sequence based on a collection of its substrings observed through a noisy channel. This problem of reconstructing sequences from traces was first investigated in the noiseless setting under the name of “Markov type” analysis. Here, we explain the connection between the problem and the problem of DNA synthesis and sequencing, and introduce the notion of a DNA storage channel. We analyze the number of sequence equivalence classes under the channel mapping and propose new asymmetric coding techniques to combat the effects of synthesis noise. In our analysis, we make use of Ehrhart theory for rational polytopes.
Unlimited parity alternating partitions

We introduce a new type of partition that consists of partitions whose different parts alternate in parity (e.g., 3 + 2 + 2 + 1 + 1). Various properties of this partition function are studied. In p...
Compositional Attention Networks for Machine Reasoning

We present the MAC network, a novel fully differentiable neural network architecture, designed to facilitate explicit and expressive reasoning. MAC moves away from monolithic black-box neural architectures towards a design that encourages both transparency and versatility. The model approaches problems by decomposing them into a series of attention-based reasoning steps, each performed by a novel recurrent Memory, Attention, and Composition (MAC) cell that maintains a separation between control and memory. By stringing the cells together and imposing structural constraints that regulate their interaction, MAC effectively learns to perform iterative reasoning processes that are directly inferred from the data in an end-to-end approach. We demonstrate the model's strength, robustness and interpretability on the challenging CLEVR dataset for visual reasoning, achieving a new state-of-the-art 98.9% accuracy, halving the error rate of the previous best model. More importantly, we show that the model is computationally-efficient and data-efficient, in particular requiring 5x less data than existing models to achieve strong results.
Identifying conditional causal effects

This paper concerns the assessment of the effects of actions from a combination of nonexperimental data and causal assumptions encoded in the form of a directed acyclic graph in which some variables are presumed to be unobserved. We provide a procedure that systematically identifies cause effects between two sets of variables conditioned on some other variables, in time polynomial in the number of variables in the graph. The identifiable conditional causal effects are expressed in terms of the observed joint distribution.
Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the $\mathrm {P} \neq \text {NP}$ conjecture which asserts that $\text {NP}$ is a nonnegligible subset of $\text {EXP}$ . Cai et al. (1997) showed that the analogue of this hypothesis in $\mathrm {P}$ is false. In particular, they showed that $\text {NTIME}[n^{1/11}]$ has measure 0 in $\mathrm {P}$ . We improve on their result to show that the class of all languages decidable in nondeterministic sublinear time has measure 0 in $\mathrm {P}$ . Our result is based on DNF width and holds for all four major notions of measure on $\mathrm {P}$ .
Borel equivalence relations in the space of bounded operators

We consider various notions of equivalence in the space of bounded operators on a Hilbert space, in particular modulo finite rank, modulo Schatten $p$-class, and modulo compact. Using Hjorth's theory of turbulence, the latter two are shown to be not classifiable by countable structures, while the first is not reducible to the orbit equivalence relation of any Polish group action. The results for modulo finite rank and modulo compact operators are also shown for the restrictions of these equivalence relations to the space of projection operators.
Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-Rank Matrix Completion

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well-known restricted isometry property cannot be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $\nu $ , the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nr\nu \log ^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different 3-D data and protein molecules validate the effectiveness and efficiency of the proposed algorithms.
Maximum likelihood degree of Fermat hypersurfaces via Euler characteristics

Maximum likelihood degree of a projective variety is the number of critical points of a general likelihood function. In this note, we compute the Maximum likelihood degree of Fermat hypersurfaces. We give a formula of the Maximum likelihood degree in terms of the constants $\beta_{\mu, \nu}$, which is defined to be the number of complex solutions to the system of equations $z_1^\nu=z_2^\nu=\cdots=z_\mu^\nu=1$ and $z_1+\cdots +z_\mu+1=0$.
The Mean Interference-to-Signal Ratio and Its Key Role in Cellular and Amorphous Networks

We introduce a simple yet powerful and versatile analytical framework for approximating the SIR distribution in the downlink of cellular systems. It is based on the mean interference-to-signal ratio and yields the horizontal gap (SIR gain) between the SIR distribution in question and a reference SIR distribution. As applications, we determine the SIR gain for base station silencing, cooperation, and lattice deployment over a baseline architecture that is based on a Poisson deployment of base stations and strongest-base station association. The applications demonstrate that the proposed approach unifies several recent results and provides a convenient framework for the analysis and comparison of future network architectures and transmission schemes, including amorphous networks where a user is served by multiple base stations and, consequently, (hard) cell association becomes less relevant.
Between Pure and Approximate Differential Privacy

We show a new lower bound on the sample complexity of (e,δ)-differentially private algorithms that accurately answer statistical queries on high-dimensional databases. The novelty of our bound is that it depends optimally on the parameter δ, which loosely corresponds to the probability that the algorithm fails to be private, and is the first to smoothly interpolate between approximate differential privacy (δ >0) and pure differential privacy (δ= 0). Specifically, we consider a database D ∈{±1}n×d and its one-way marginals, which are the d queries of the form “What fraction of individual records have the i-th bit set to +1?” We show that in order to answer all of these queries to within error ±α (on average) while satisfying (e,δ)-differential privacy for some function δ such that δ≥2−o(n) and δ≤1/n1+Ω(1), it is necessary that \[n≥Ω (\frac{√dlog(1/δ)}{αe}).\] This bound is optimal up to constant factors. This lower bound implies similar new bounds for problems like private empirical risk minimization and private PCA. To prove our lower bound, we build on the connection between fingerprinting codes and lower bounds in differential privacy (Bun, Ullman, and Vadhan, STOC’14). In addition to our lower bound, we give new purely and approximately differentially private algorithms for answering arbitrary statistical queries that improve on the sample complexity of the standard Laplace and Gaussian mechanisms for achieving worst-case accuracy guarantees by a logarithmic factor.
Density Modeling of Images using a Generalized Normalization Transformation

Abstract: We introduce a parametric nonlinear transformation that is well-suited for Gaussianizing data from natural images. After a linear transformation of the data, each component is normalized by a pooled activity measure, computed by exponentiating a weighted sum of rectified and exponentiated components and an additive constant. We optimize the parameters of this transformation (linear transform, exponents, weights, constant) over a database of natural images, directly minimizing the negentropy of the responses. We find that the optimized transformation successfully Gaussianizes the data, achieving a significantly smaller mutual information between transformed components than previous methods including ICA and radial Gaussianization. The transformation is differentiable and can be efficiently inverted, and thus induces a density model on images. We show that samples of this model are visually similar to samples of natural image patches. We also demonstrate the use of the model as a prior density in removing additive noise. Finally, we show that the transformation can be cascaded, with each layer optimized (unsupervised) using the same Gaussianization objective, to capture additional probabilistic structure.
Vakhitov–Kolokolov and energy vanishing conditions for linear instability of solitary waves in models of classical self-interacting spinor fields

We study the linear stability of localized modes in self-interacting spinor fields, analysing the spectrum of the operator corresponding to linearization at solitary waves. Following the generalization of the Vakhitov–Kolokolov approach, we show that the bifurcation of real eigenvalues from the origin is completely characterized by the Vakhitov–Kolokolov condition dQ/dω = 0 and by the vanishing of the energy functional. We give the numerical data on the linear stability in the generalized Gross–Neveu model and the generalized massive Thirring model in the charge-subcritical, charge-critical and charge-supercritical cases, illustrating the agreement with the Vakhitov–Kolokolov and the energy vanishing conditions.
List decoding Reed-Muller codes over small fields

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a nite eld F. The Reed-Muller code RMF(n;d) is dened by n-variate degree-d polynomials over F. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime eld F = Fp, constant degree d and large n. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by (d) the normalized minimal distance of RMF(n;d), then the number of codewords in any ball of radius (d) " is bounded by c = c(p;d;") independent of n. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of F = F2; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of d = 2. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e d, we show that the number of codewords of RMF(n;d) in a ball of radius (e) " is bounded by exp(c n d e ), where c = c(p;d;") is independent of n. The dependence on n is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who proved similar bounds over F2. The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the SchwartzZippel lemma to compositions of polynomials.
Determining the first order perturbation of a polyharmonic operator on admissible manifolds

Abstract We consider the inverse boundary value problem for the first order perturbation of the polyharmonic operator L g , X , q , with X being a W 1 , ∞ vector field and q being an L ∞ function on compact Riemannian manifolds with boundary which are conformally embedded in a product of the Euclidean line and a simple manifold. We show that the knowledge of the Dirichlet-to-Neumann map determines X and q uniquely. The method is based on the construction of complex geometrical optics solutions using the Carleman estimate for the Laplace–Beltrami operator due to Dos Santos Ferreira, Kenig, Salo and Uhlmann. Notice that the corresponding uniqueness result does not hold for the first order perturbation of the Laplace–Beltrami operator.
The Penetration Effect of Connected Automated Vehicles in Urban Traffic: An Energy Impact Study

Earlier work has established a decentralized framework of optimally controlling connected and automated vehicles (CAVs) crossing an urban intersection without using explicit traffic signaling. The proposed solution is capable of minimizing energy consumption subject to a throughput maximization requirement. In this paper, we address the problem of optimally controlling CAVs under mixed traffic conditions where both CAVs and human-driven vehicles (non-CAVs) travel on the roads, so as to minimize energy consumption while guaranteeing safety constraints. The impact of CAVs on overall energy consumption is also investigated under different traffic scenarios. The benefit from CAV penetration (i.e., the fraction of CAVs relative to all vehicles) is validated through simulation in MATLAB and VISSIM. The results indicate that the energy efficiency improvement becomes more significant as the CAV penetration rate increases, while the significance diminishes as the traffic becomes heavier.
REACT to Cyber Attacks on Power Grids

Motivated by the recent cyber attack on the Ukrainian power grid, we study cyber attacks on power grids that affect both the physical infrastructure and the data at the control center–which therefore are cyber-physical in nature. In particular, we assume that an adversary attacks an area by: (i) remotely disconnecting some lines within the attacked area, and (ii) modifying the information received from the attacked area to mask the line failures and hide the attacked area from the control center. For the latter, we consider two types of attacks: (i) data distortion: which distorts the data by adding powerful noise to the actual data, and (ii) data replay: which replays a locally consistent old data instead of the actual data. We use the DC power flow model and prove that the problem of finding the set of line failures given the phase angles of the nodes outside of the attacked area is strongly NP-hard, even when the attacked area is known. However, we introduce the polynomial time REcurrent Attack Containment and deTection (REACT) Algorithm to approximately detect the attacked area and line failures after a cyber-physical attack. We numerically show that it performs well in detecting the attacked area, and detecting single, double, and triple line failures in small and large attacked areas.
A performance spectrum for parallel computational frameworks that solve PDEs

Important computational physics problems are often large-scale in nature, and it is highly desirable to have robust and high performing computational frameworks that can quickly address these problems. However, it is no trivial task to determine whether a computational framework is performing efficiently or is scalable. The aim of this paper is to present various strategies for better understanding the performance of any parallel computational frameworks for solving PDEs. Important performance issues that negatively impact time-to-solution are discussed, and we propose a performance spectrum analysis that can enhance one's understanding of critical aforementioned performance issues. As proof of concept, we examine commonly used finite element simulation packages and software and apply the performance spectrum to quickly analyze the performance and scalability across various hardware platforms, software implementations, and numerical discretizations. It is shown that the proposed performance spectrum is a versatile performance model that is not only extendable to more complex PDEs such as hydrostatic ice sheet flow equations, but also useful for understanding hardware performance in a massively parallel computing environment. Potential applications and future extensions of this work are also discussed.
Tight relaxations for polynomial optimization and Lagrange multiplier expressions

This paper proposes tight semidefinite relaxations for polynomial optimization. The optimality conditions are investigated. We show that generally Lagrange multipliers can be expressed as polynomial functions in decision variables over the set of critical points. The polynomial expressions are determined by linear equations. Based on these expressions, new Lasserre type semidefinite relaxations are constructed for solving the polynomial optimization. We show that the hierarchy of new relaxations has finite convergence, or equivalently, the new relaxations are tight for a finite relaxation order.
Increasing consecutive patterns in words

We show how to enumerate words in $$1^{m_1} \ldots n^{m_n}$$ that avoid the increasing consecutive pattern $$12 \ldots r$$ for any $$r \ge 2$$. Our approach yields an $$O(n^{s+1})$$ algorithm to enumerate words in $$1^s \ldots n^s$$, avoiding the consecutive pattern $$1\ldots r$$, for anys, and anyr. This enables us to supply many more terms to quite a few OEIS sequences and create new ones. We also treat the more general case of counting words with a specified number of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms.
What is it like down there?: generating dense ground-level views and image features from overhead imagery using conditional generative adversarial networks

This paper investigates conditional generative adversarial networks (cGANs) to overcome a fundamental limitation of using geotagged media for geographic discovery, namely its sparse and uneven spatial distribution. We train a cGAN to generate ground-level views of a location given overhead imagery. We show the "fake" ground-level images are natural looking and are structurally similar to the real images. More significantly, we show the generated images are representative of the locations and that the representations learned by the cGANs are informative. In particular, we show that dense feature maps generated using our framework are more effective for land-cover classification than approaches which spatially interpolate features extracted from sparse ground-level images. To our knowledge, ours is the first work to use cGANs to generate ground-level views given overhead imagery in order to explore the benefits of the learned representations.
A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction

In this paper we define a metric distance between probability distributions on two distinct finite sets of possibly different cardinalities. The metric is defined in terms of a joint distribution on the product of the two sets, which has the two given distributions as its marginals, and has minimum entropy. Computing the metric exactly turns out to be NP-hard. Therefore an efficient greedy algorithm is presented for finding an upper bound on the distance. We then study the problem of optimal order reduction in the metric defined here. It is shown that every optimal reduced-order approximation must be an aggregation of the original distribution, and that optimal reduced order approximation is equivalent to finding an aggregation with maximum entropy. This problem also turns out to be NP-hard, so again a greedy algorithm is constructed for finding a suboptimal reduced order approximation. Taken together, all the results presented here permit the approximation of an independent and identically distributed (i.i.d.) process over a set of large cardinality by another i.i.d. process over a set of smaller cardinality. In future work, attempts will be made to extend this work to Markov processes over finite sets.
Affine geometric crystals in unipotent loop groups

We study products of the affine geometric crystal of type A corresponding to symmetric powers of the standard representation. The quotient of this product by the R-matrix action is constructed inside the unipotent loop group. This quotient crystal has a semi-infinite limit, where the crystal structure is described in terms of limit ratios previously appearing in the study of total positivity of loop groups.
Chance-Constrained ADMM Approach for Decentralized Control of Distributed Energy Resources

Distribution systems are undergoing a dramatic transition from a passive circuit that routinely disseminates electric power among downstream nodes to the system with distributed energy resources. The distributed energy resources come in a variety of technologies and typically include photovoltaic (PV) arrays, thermostatically controlled loads, energy storage units. Often these resources are interfaced with the system via inverters that can adjust active and reactive power injections, thus supporting the operational performance of the system. This paper designs a control policy for such inverters using the local power flow measurements. The control actuates active and reactive power injections of the inverter-based distributed energy resources. This strategy is then incorporated into a chance-constrained, decentralized optimal power flow formulation to maintain voltage levels and power flows within their limits and to mitigate the volatility of (PV) resources. Our method is shown to improve voltage regulation compliance and reduce power losses.
Heffter Arrays and Biembedding Graphs on Surfaces

A Heffter array is an $m \times n$ matrix with nonzero entries from $\mathbb{Z}_{2mn+1}$ such that i) every row and column sum to 0, and ii) exactly one of each pair $\{x,-x\}$ of nonzero elements appears in the array. We construct some Heffter arrays. These arrays are used to build current graphs used in topological graph theory. In turn, the current graphs are used to embed the complete graph $K_{2mn+1}$ so that the faces can be 2-colored, called a biembedding. Under certain conditions each color class forms a cycle system. These generalize biembeddings of Steiner triple systems. We discuss some variations including Heffter arrays with empty cells, embeddings on nonorientable surfaces, complete multigraphs, and using integer arithmetic in place of modular arithmetic.
Approximation and Orthogonality in Sobolev Spaces on a Triangle

Approximation by polynomials on a triangle is studied in the Sobolev space $$W_2^r$$ that consists of functions whose derivatives of up to r-th order have bounded $$L^2$$ norm. The first part aims at understanding the orthogonal structure in the Sobolev space on the triangle, which requires explicit construction of an inner product that involves derivatives and its associated orthogonal polynomials, so that the projection operators of the corresponding Fourier orthogonal expansion commute with partial derivatives. The second part establishes the sharp estimate for the error of polynomial approximation in $$W_2^r$$ , when $$r = 1$$ and $$r=2$$ , where the polynomials of approximation are the partial sums of the Fourier expansions in orthogonal polynomials of the Sobolev space.
Interpolation on Symmetric Spaces Via the Generalized Polar Decomposition

We construct interpolation operators for functions taking values in a symmetric space—a smooth manifold with an inversion symmetry about every point. Key to our construction is the observation that every symmetric space can be realized as a homogeneous space whose cosets have canonical representatives by virtue of the generalized polar decomposition—a generalization of the well-known factorization of a real nonsingular matrix into the product of a symmetric positive-definite matrix times an orthogonal matrix. By interpolating these canonical coset representatives, we derive a family of structure-preserving interpolation operators for symmetric space-valued functions. As applications, we construct interpolation operators for the space of Lorentzian metrics, the space of symmetric positive-definite matrices, and the Grassmannian. In the case of Lorentzian metrics, our interpolation operators provide a family of finite elements for numerical relativity that are frame-invariant and have signature which is guaranteed to be Lorentzian pointwise. We illustrate their potential utility by interpolating the Schwarzschild metric numerically.
Comparing Hecke Coefficients of Automorphic Representations

We prove a number of statistical properties of Hecke coefficients for unitary cuspidal representations on $\operatorname{GL}(2)$ over number fields (unconditionally) and on $\operatorname{GL}(n)$ over number fields (conditionally, either assuming the Ramanujan conjecture, or the functoriality of $\pi\otimes\pi^\vee$). Using partial bounds on Hecke coefficients, properties of Rankin-Selberg $L$-functions, and instances of Langlands functoriality, we obtain bounds on the set of places where (linear combinations of) Hecke coefficients are bounded above (or below). We furthermore prove a number of consequences: we obtain an improved answer to a question of Serre about the occurrence of large Hecke eigenvalues of Maass forms ($|a_p|>1$ for density at least $0.00135$ set of primes), we prove the existence of negative Hecke coefficients over arbitrary number fields, and we obtain distributional results on the Hecke coefficients $a_v$ when $v$ varies in certain congruence or Galois classes. E.g., if $E$ is an elliptic curve without CM we show that $a_p(E)<0$ for a density $\geq \frac{1}{8}$ of primes $p\equiv a\pmod{n}$, or density $\geq \frac{1}{16}$ of primes of the form $p=m^2+27n^2$.
Further Limitations of the Known Approaches for Matrix Multiplication

We consider the techniques behind the current best algorithms for matrix multiplication. Our results are threefold. (1) We provide a unifying framework, showing that all known matrix multiplication running times since 1986 can be achieved from a single very natural tensor - the structural tensor T_q of addition modulo an integer q. (2) We show that if one applies a generalization of the known techniques (arbitrary zeroing out of tensor powers to obtain independent matrix products in order to use the asymptotic sum inequality of Schonhage) to an arbitrary monomial degeneration of T_q, then there is an explicit lower bound, depending on q, on the bound on the matrix multiplication exponent omega that one can achieve. We also show upper bounds on the value alpha that one can achieve, where alpha is such that n * n^alpha * n matrix multiplication can be computed in n^{2+o(1)} time. (3) We show that our lower bound on omega approaches 2 as q goes to infinity. This suggests a promising approach to improving the bound on omega: for variable q, find a monomial degeneration of T_q which, using the known techniques, produces an upper bound on omega as a function of q. Then, take q to infinity. It is not ruled out, and hence possible, that one can obtain omega=2 in this way.