cssi/SciSciGPT-SciSciNet huggingface dataset:
Algebraic methods of classifying directed graphical models

In information theory, structural system constraints are frequently described in the form of a directed acyclic graphical model (DAG). This paper addresses the question of classifying DAGs up to an isomorphism. By considering Gaussian densities, the question reduces to verifying equality of certain algebraic varieties. A question of computing equations for these varieties has been previously raised in the literature. Here it is shown that the most natural method adds spurious components with singular principal minors, proving a conjecture of Sullivant. This characterization is used to establish an algebraic criterion for isomorphism, and to provide a randomized algorithm for checking that criterion. Results are applied to produce a list of the isomorphism classes of tree models on 4 and 5 nodes.
Actor-Action Semantic Segmentation with Grouping Process Models

Actor-action semantic segmentation made an important step toward advanced video understanding: what action is happening, who is performing the action, and where is the action happening in space-time. Current methods based on layered CRFs for this problem are local and unable to capture the long-ranging interactions of video parts. We propose a new model that combines the labeling CRF with a supervoxel hierarchy, where supervoxels at various scales provide cues for possible groupings of nodes in the CRF to encourage adaptive and long-ranging interactions. The new model defines a dynamic and continuous process of information exchange: the CRF influences what supervoxels in the hierarchy are active, and these active supervoxels, in turn, affect the connectivities in the CRF, we hence call it a grouping process model. By further incorporating the video-level recognition, the proposed method achieves a large margin of 60% relative improvement over the state of the art on the recent A2D large-scale video labeling dataset, which demonstrates the effectiveness of our modeling.
Bipodal structure in oversaturated random graphs

We study the asymptotics of large simple graphs constrained by the limiting density of edges and the limiting subgraph density of an arbitrary xed graph H. We prove that, for all but nitely many values of the edge density, if the density of H is constrained to be slightly higher than that for the corresponding Erd} os-R enyi graph, the typical large graph is bipodal with parameters varying analytically with the densities. Asymptotically, the parameters depend only on the degree sequence of H.
Rigid inner forms vs isocrystals

We compare two statements of the refined local Langlands correspondence for connected reductive groups defined over a p-adic field -- one involving Kottwitz's set B(G) of isocrystals with additional structure, and one involving the cohomology set H^1(u -> W,Z -> G) introduced in arXiv:1304.3292. We show that if either statement is valid for all connected reductive groups, then so is the other. We also discuss how the second statement depends on the choice of element of H^1(u -> W,Z -> G).
Certain upper bounds on the eigenvalues associated with prolate spheroidal wave functions

Abstract Prolate spheroidal wave functions (PSWFs) play an important role in various areas, from physics (e.g. wave phenomena, fluid dynamics) to engineering (e.g. signal processing, filter design). One of principal reasons for the importance of PSWFs is that they are a natural and efficient tool for computing with bandlimited functions, that frequently occur in the above-mentioned areas. This is due to the fact that PSWFs are the eigenfunctions of the integral operator representing time-limiting followed by low-passing. Needless to say, the behavior of this operator is to a large degree governed by the decay rate of its eigenvalues. Therefore, this decay rate plays a crucial role in the related theory and applications – for example, in construction of quadratures, interpolation, filter design, etc. The significance of PSWFs and, in particular, of the decay rate of the eigenvalues of the associated integral operator, was realized at least half a century ago. Nevertheless, perhaps surprisingly, despite vast numerical experience and existence of several asymptotic expansions, non-trivial explicit upper bounds on the magnitudes of the eigenvalues in various regimes have been missing for decades. The principal goal of this paper is to close this gap in the theory of PSWFs. We analyze the integral operator associated with PSWFs, to derive fairly tight non-asymptotic upper bounds on the magnitudes of its eigenvalues. Our results are illustrated via several numerical experiments.
Burst Denoising with Kernel Prediction Networks

We present a technique for jointly denoising bursts of images taken from a handheld camera. In particular, we propose a convolutional neural network architecture for predicting spatially varying kernels that can both align and denoise frames, a synthetic data generation approach based on a realistic noise formation model, and an optimization guided by an annealed loss function to avoid undesirable local minima. Our model matches or outperforms the state-of-the-art across a wide range of noise levels on both real and synthetic data.
L-Kuramoto–Sivashinsky SPDEs vs. time-fractional SPIDEs: Exact continuity and gradient moduli, 1/2-derivative criticality, and laws

Abstract We establish exact, dimension-dependent, spatio-temporal, uniform and local moduli of continuity for (1) the fourth order L-Kuramoto–Sivashinsky (L-KS) SPDEs and for (2) the time-fractional stochastic partial integro-differential equations (SPIDEs), driven by the space–time white noise in one-to-three dimensional spaces. Both classes were introduced—with Brownian-time-type kernel formulations—by Allouba in a series of articles starting in 2006, where he presented class (2) in its rigorous stochastic integral equations form. He proved existence, uniqueness, and sharp spatio-temporal Holder regularity for the above two classes of equations in d = 1 , 2 , 3 . We show that both classes are ( 1 / 2 ) − Holder continuously differentiable in space when d = 1 , and we give the exact uniform and local moduli of continuity for the gradient in both cases. This is unprecedented for SPDEs driven by the space–time white noise. Our results on exact moduli show that the half-derivative SPIDE is a critical case. It signals the onset of rougher modulus regularity in space than both time-fractional SPIDEs with time-derivatives of order 1 / 2 and L-KS SPDEs. This is despite the fact that they all have identical spatial Holder regularity, as shown earlier by Allouba. Moreover, we show that the temporal laws governing (1) and (2) are fundamentally different. We relate L-KS SPDEs to the Houdre-Villa bifractional Brownian motion, yielding a Chung-type law of the iterated logarithm for these SPDEs. We use the underlying explicit kernels and spectral/harmonic analysis to prove our results. On one hand, this work builds on the recent works on delicate sample path properties of Gaussian random fields. On the other hand, it builds on and complements Allouba's earlier works on (1) and (2). Similar regularity results hold for the Allen–Cahn nonlinear members of (1) and (2) on compacts via change of measure.
Optimizing performance of the deconvolution model reduction for large ODE systems

We investigate the numerical performance of the regularized deconvolution closure introduced recently by the authors. The purpose of the closure is to furnish constitutive equations for Irving-Kirkwood-Noll procedure, a well known method for deriving continuum balance equations from the Newton’s equations of particle dynamics. A version of this procedure used in the paper relies on spatial averaging developed by Hardy, and independently by Murdoch and Bedeaux. The constitutive equations for the stress are given as a sum of nonlinear operator terms acting on the mesoscale average density and velocity. Each term is a “convolution sandwich” containing the deconvolution operator, a composition or a product operator, and the convolution (averaging) operator. Deconvolution is constructed using filtered regularization methods from the theory of ill-posed problems. The purpose of regularization is to ensure numerical stability. The particular technique used for numerical experiments is truncated singular value decomposition (SVD). The accuracy of the constitutive equations depends on several parameters: the choice of the averaging window function, the value of the mesoscale resolution parameter, scale separation, the level of truncation of singular values, and the level of spectral filtering of the averages. We conduct numerical experiments to determine the effect of each parameter on the accuracy and efficiency of the method. Partial error estimates are also obtained.
Reachable Set Estimation and Verification for Neural Network Models of Nonlinear Dynamic Systems

Neural networks have been widely used to solve complex real-world problems. Due to the complex, nonlinear, non-convex nature of neural networks, formal safety and robustness guarantees for the behaviors of neural network systems are crucial for their applications in safety-critical systems. In this paper, the reachable set estimation and safety verification problems for Nonlinear Autoregressive-Moving Average (NARMA) models in the forms of neural networks are addressed. The neural networks involved in the model are a class of feed-forward neural networks called Multi-Layer Perceptrons (MLPs). By partitioning the input set of an MLP into a finite number of cells, a layer-by-layer computation algorithm is developed for reachable set estimation of each individual cell. The union of estimated reachable sets of all cells forms an over-approximation of the reachable set of the MLP. Furthermore, an iterative reachable set estimation algorithm based on reachable set estimation for MLPs is developed for NARMA models. The safety verification can be performed by checking the existence of non-empty intersections between unsafe regions and the estimated reachable set. Several numerical examples are provided to illustrate the approach.
Deuterium microbomb rocket propulsion

Abstract Large scale manned space flight within the solar system is still confronted with the solution of two problems: (1) A propulsion system to transport large payloads with short transit times between different planetary orbits. (2) A cost effective lifting of large payloads into earth orbit. For the solution of the first problem a deuterium fusion bomb propulsion system is proposed where a thermonuclear detonation wave is ignited in a small cylindrical assembly of deuterium with a gigavolt-multimegaampere proton beam, drawn from the magnetically insulated spacecraft acting in the ultrahigh vacuum of space as a gigavolt capacitor. For the solution of the second problem, the ignition is done by argon ion lasers driven by high explosives, with the lasers destroyed in the fusion explosion and becoming part of the exhaust.
Searching for TeV gamma-ray emission associated with IceCube high-energy neutrinos using VERITAS

A clue to finding the long-sought sources of cosmic rays is the recent observation of an astrophysical flux of high-energy neutrinos by the IceCube detector, since these possibly originate in hadronic interactions at cosmic-ray accelerators. While the neutrino sky map shows no significant indication of point sources so far, it is possible to utilize the sensitivity of Imaging Air Cherenkov Telescope (IACT) arrays, such as VERITAS, to search for hadronic gamma-ray emission from the neutrino directions. Over the last 2 years, the positions of neutrino events detected by IceCube have been observed using the VERITAS array. Observations have been limited to muon neutrino events, since their typical angular reconstruction uncertainty is below 1◦, smaller than the 3.5◦ diameter of the VERITAS field of view. The location of VERITAS further constrains the neutrino event positions that can be observed to those located in the northern sky, or at moderate southern declinations. The list of observed positions was selected from published results and a set of high-energy muon tracks provided by IceCube. We present the current status and some preliminary results from this program.
Towards controlled Fizeau observations with the Large Binocular Telescope

The Large Binocular Telescope Interferometer (LBTI) can perform Fizeau interferometry in the focal plane, which accesses spatial information out to the LBT's full 22.7-m edge-to-edge baseline. This mode has previously been used to obtain science data, but has been limited to observations where the optical path difference (OPD) between the two beams is not controlled, resulting in unstable fringes on the science detectors. To maximize the science return, we are endeavoring to stabilize the OPD and tip-tilt variations and make the LBTI Fizeau mode optimized and routine. Here we outline the optical configuration of LBTI's Fizeau mode and our strategy for commissioning this observing mode.
Towards a Predictive Hybrid RANS/LES Framework

Predictive simulation of many complex flows requires moving beyond Reynolds-averaged Navier-Stokes (RANS) based models to representations resolving at least some scales of turbulence in at least some regions of the flow. To resolve turbulence where necessary while avoiding the cost of performing large eddy simulation (LES) everywhere, a broad range of hybrid RANS/LES methods have been developed. While successful in some situations, existing methods exhibit a number of deficiencies which limit their predictive capability in many cases of interest, for instance in many flows involving smooth wall separation. These deficiencies result from inappropriate blending approaches and resulting inconsistencies between the resolved and modeled turbulence as well as errors inherited from the underlying RANS and LES models. This work details these problems and their effects in hybrid simulations, and develops a modeling paradigm aimed at overcoming these challenges. The new approach discards typical blending approaches in favor of a hybridization strategy in which the RANS and LES model components act through separate models formulated using the mean and fluctuating velocity, respectively. Further, a forcing approach in which fluctuating content is actively transferred from the modeled to the resolved scales is introduced. Finally, the model makes use of an anisotropic LES model that is intended to represent the effects of grid anisotropy. The model is demonstrated on fully-developed, incompressible channel flow and shown to be very promising.
Incentive design for learning in user-recommendation systems with time-varying states

We consider the problem of how strategic users with asymmetric information can learn an underlying time- varying state in a user-recommendation system. Users who observe private signals about the state, sequentially make a decision about buying a product whose value varies with time in an ergodic manner. We formulate the team problem as an instance of decentralized stochastic control problem and characterize its optimal policies. With strategic users, we design incentives such that users reveal their true private signals, so that the gap between the strategic and team objective is small and the overall expected incentive payments are also small.
The random k cycle walk on the symmetric group

We study the random walk on the symmetric group $$S_n$$ generated by the conjugacy class of cycles of length k. We show that the convergence to uniform measure of this walk has a cut-off in total variation distance after $$\frac{n}{k}\log n$$ steps, uniformly in $$k = o(n)$$ as $$n \rightarrow \infty $$ . The analysis follows from a new asymptotic estimation of the characters of the symmetric group evaluated at cycles.
Image Restoration Using Total Variation Regularized Deep Image Prior

In the past decade, sparsity-driven regularization has led to significant improvements in image reconstruction. Traditional regularizers, such as total variation (TV), rely on analytical models of sparsity. However, increasingly the field is moving towards trainable models, inspired from deep learning. Deep image prior (DIP) is a recent regularization framework that uses a convolutional neural network (CNN) architecture without data-driven training. This paper extends the DIP framework by combining it with the traditional TV regularization. We show that the inclusion of TV leads to considerable performance gains when tested on several traditional restoration tasks such as image denoising and deblurring.
Towards Fast Computation of Certified Robustness for ReLU Networks

Verifying the robustness property of a general Rectified Linear Unit (ReLU) network is an NP-complete problem [Katz, Barrett, Dill, Julian and Kochenderfer CAV17]. Although finding the exact minimum adversarial distortion is hard, giving a certified lower bound of the minimum distortion is possible. Current available methods of computing such a bound are either time-consuming or delivering low quality bounds that are too loose to be useful. In this paper, we exploit the special structure of ReLU networks and provide two computationally efficient algorithms Fast-Lin and Fast-Lip that are able to certify non-trivial lower bounds of minimum distortions, by bounding the ReLU units with appropriate linear functions Fast-Lin, or by bounding the local Lipschitz constant Fast-Lip. Experiments show that (1) our proposed methods deliver bounds close to (the gap is 2-3X) exact minimum distortion found by Reluplex in small MNIST networks while our algorithms are more than 10,000 times faster; (2) our methods deliver similar quality of bounds (the gap is within 35% and usually around 10%; sometimes our bounds are even better) for larger networks compared to the methods based on solving linear programming problems but our algorithms are 33-14,000 times faster; (3) our method is capable of solving large MNIST and CIFAR networks up to 7 layers with more than 10,000 neurons within tens of seconds on a single CPU core. In addition, we show that, in fact, there is no polynomial time algorithm that can approximately find the minimum $\ell_1$ adversarial distortion of a ReLU network with a $0.99\ln n$ approximation ratio unless $\mathsf{NP}$=$\mathsf{P}$, where $n$ is the number of neurons in the network.
Highly tunable efficient second-harmonic generation in a lithium niobate nanophotonic waveguide

Highly tunable coherent light generation is crucial for many important photonic applications. Second-harmonic generation (SHG) is a dominant approach for this purpose, which, however, exhibits a trade-off between conversion efficiency and wavelength tunability in a conventional nonlinear platform. Recent development of the integrated lithium niobate (LN) technology makes it possible to achieve a large wavelength tuning while maintaining a high conversion efficiency. Here we report on-chip SHG that simultaneously achieves a large tunability and a high conversion efficiency inside a single device. We utilize the unique strong thermo-optic birefringence of LN to achieve flexible temperature tuning of type-I intermodal phase matching. We experimentally demonstrate spectral tuning with a tuning slope of 0.84 nm/K for a telecom-band pump, and a nonlinear conversion efficiency of 4.7% W−1, in an LN nanophotonic waveguide only 8 mm long. Our device shows great promise for efficient on-chip wavelength conversion to produce highly tunable coherent visible light for broad applications, while taking advantage of the mature and cost-effective telecom laser technology.
On the estimation and control of human body composition

Obesity is a chronic disease that can lead to an increased risk of other serious chronic diseases and even death. We present switching and time-delayed feedback-based model-free control methods for...
VIRTUAL SHADOW MODULES AND THEIR LINK INVARIANTS

We introduce an algebra ℤ[X, S] associated to a pair X, S of a virtual birack X and X-shadow S. We use modules over ℤ[X, S] to define enhancements of the virtual birack shadow counting invariant, extending the birack shadow module invariants to virtual case. We repeat this construction for the twisted virtual case. As applications, we show that the new invariants can detect orientation reversal and are not determined by the knot group, the Arrow polynomial and the Miyazawa polynomial, and that the twisted version is not determined by the twisted Jones polynomial.
Generalized eigenvectors of isospectral transformations, spectral equivalence and reconstruction of original networks

Abstract Isospectral transformations (IT) of matrices and networks allow for compression of either object while keeping all the information about their eigenvalues and eigenvectors. We analyze here what happens to generalized eigenvectors under isospectral transformations and to what extent the initial network can be reconstructed from its compressed image under IT. We also generalize and essentially simplify the proof that eigenvectors are invariant under isospectral transformations and generalize and clarify the notion of spectral equivalence of networks.
A Proof of the Bomber Problem's Spend-It-All Conjecture

Abstract The Bomber Problem concerns optimal sequential allocation of partially effective ammunition x while under attack from enemies arriving according to a Poisson process over a time interval of length t. In the doubly continuous setting, in certain regions of (x, t)-space we are able to solve the integral equation defining the optimal survival probability and find the optimal allocation function K(x, t) exactly in these regions. As a consequence, we complete the proof of the “spend-it-all” conjecture of Bartroff et al. (2010b), which gives the boundary of the region where K(x, t) = x.
Systems of sets of lengths of Puiseux monoids

Abstract In this paper we study the system of sets of lengths of non-finitely generated atomic Puiseux monoids (a Puiseux monoid is an additive submonoid of Q ≥ 0 ). We begin by presenting a BF-monoid M with full system of sets of lengths, which means that for each subset S of Z ≥ 2 there exists an element x ∈ M whose set of lengths L ( x ) is S. It is well known that systems of sets of lengths do not characterize numerical monoids. Here, we prove that systems of sets of lengths do not characterize non-finitely generated atomic Puiseux monoids. In a recent paper, Geroldinger and Schmid found the intersection of systems of sets of lengths of numerical monoids. Motivated by this, we extend their result to the setting of atomic Puiseux monoids. Finally, we relate the sets of lengths of the Puiseux monoid P = 〈 1 / p | p is prime 〉 with the Goldbach's conjecture ; in particular, we show that L ( 2 ) is precisely the set of Goldbach's numbers.
Bounded gaps between products of distinct primes

Let $$r \ge 2$$ be an integer. We adapt the Maynard–Tao sieve to produce the asymptotically best-known bounded gaps between products of r distinct primes. Our result applies to positive-density subsets of the primes that satisfy certain equidistribution conditions. This improves on the work of Thorne and Sono.
OCCAM: An Optimization Based Approach to Network Inference

We study the problem of inferring the structure of a communication network based only on network measurements made from a set of hosts situated at the network periphery. Our novel approach called "OCCAM" is based on the principle of occam's razor and finds the "simplest" network that explains the observed network measurements. OCCAM infers the internal topology of a communication network, including the internal nodes and links of the network that are not amenable to direct measurement. In addition to network topology, OCCAM infers the routing paths that packets take between the hosts. OCCAM uses path metrics measurable from the hosts and expresses the observed measurements as constraints of a mixed-integer bilinear optimization problem that can then be feasibly solved to yield the network topology and the routing paths. We empirically validate OCCAM on a wide variety of real-world ISP networks and show that its inferences agree closely with the ground truth. Specifically, OCCAM infers the topology with an average network similarity score of 93% and infers routing paths with a path edit distance of 0.20. Further, OCCAM is robust to error in its measured path metric inputs, producing high quality inferences even when 20-30% of its inputs are erroneous. Our work is a significant advance in network tomography as it proposes and empirically evaluates the first method that infers the complete network topology, rather than just logical routing trees from sources.
An optimization problem in heat conduction with minimal temperature constraint, interior heating and exterior insulation

We show the existence and optimal regularity of the optimal temperature configuration in a problem in heat conduction with minimal temperature constraint, interior heating and exterior insulation. Regularity of the two free boundaries is also studied.
Zoned HVAC control via PDE-constrained optimization

Efficiency, comfort, and convenience are three major aspects in the design of control systems for residential Heating, Ventilation, and Air Conditioning (HVAC) units. In this paper we propose an optimization-based algorithm for HVAC control that minimizes energy consumption while maintaining a desired temperature in a room. Our algorithm uses a Computer Fluid Dynamics model, mathematically formulated using Partial Differential Equations (PDEs), to describe the interactions between temperature, pressure, and air flow. Our model allows us to naturally formulate problems such as controlling the temperature of a small region of interest within a room, or to control the speed of the air flow at the vents, which are hard to describe using finite-dimensional Ordinary Partial Differential (ODE) models. Our results show that our algorithm produces significant energy savings without a decrease in comfort.
Extensions and rank-2 vector bundles on irreducible nodal curves

We generalize Bertram's work on rank two vector bundles to an irreducible projective nodal curve C. We use the natural rational map defined by to study a compactification of the moduli space of semi-stable vector bundles of rank 2 and determinant L on C. In particular, we resolve the indeterminancy of ϕL in the case deg L = 3,4 via a sequence of three blow-ups with smooth centers.
Kedlaya's Algorithm in Larger Characteristic

We show that the linear dependence on $p$ of the running time of Kedlaya's point-counting algorithm in characteristic $p$ may be reduced to $p^{1/2}$.
A Short Conceptual Proof of Narayana's Path-Counting Formula

We deduce Narayana's formula for the number of lattice paths that fit in a Young diagram as a direct consequence of the Gessel-Viennot theorem on non-intersecting lattice paths.
On Families of Periodic Orbits in the Restricted Three-Body Problem

Since Poincare, periodic orbits have been one of the most important objects in dynamical systems. However, searching them is in general quite difficult. A common way to find them is to construct families of periodic orbits which start at obvious periodic orbits. On the other hand, given two periodic orbits one might ask if they are connected by an orbit cylinder, i.e., by a one-parameter family of periodic orbits. In this article we study this question for a certain class of periodic orbits in the planar circular restricted three-body problem. Our strategy is to compare the Cieliebak–Frauenfelder–van Koert invariants which are obstructions to the existence of an orbit cylinder.
GraphMatch: Efficient Large-Scale Graph Construction for Structure from Motion

We present GraphMatch, an approximate yet efficient method for building the matching graph for large-scale structure-from-motion~(SfM) pipelines. GraphMatch leverages two priors that can predict which image pairs are likely to match, thereby making the matching process for SfM much more efficient. The first is a score computed from the distance between the Fisher vectors of any two images. The second prior is based on the graph distance between vertices in the underlying matching graph. GraphMatch combines these two priors into an iterative ``sample-and-propagate'' scheme similar to the PatchMatch algorithm. Its sampling stage uses Fisher similarity priors to guide the search for matching image pairs, while its propagation stage explores neighbors of matched pairs to find new ones with a high image similarity score. Our experiments show that GraphMatch finds the most image pairs as compared to competing, approximate methods while at the same time being the most efficient.
A Data Prism: Semi-Verified Learning in the Small-Alpha Regime

We consider a model of unreliable or crowdsourced data where there is an underlying set of $n$ binary variables, each evaluator contributes a (possibly unreliable or adversarial) estimate of the values of some subset of $r$ of the variables, and the learner is given the true value of a constant number of variables. We show that, provided an $\alpha$-fraction of the evaluators are "good" (either correct, or with independent noise rate $p 1/(2-2p)^r$. This setting can be viewed as an instance of the semi-verified learning model introduced in [CSV17], which explores the tradeoff between the number of items evaluated by each worker and the fraction of good evaluators. Our results require the number of evaluators to be extremely large, $>n^r$, although our algorithm runs in linear time, $O_{r,\epsilon}(n)$, given query access to the large dataset of evaluations. This setting and results can also be viewed as examining a general class of semi-adversarial CSPs with a planted assignment. This parameter regime where the fraction of reliable data is small, is relevant to a number of practical settings. For example, settings where one has a large dataset of customer preferences, with each customer specifying preferences for a small (constant) number of items, and the goal is to ascertain the preferences of a specific demographic of interest. Our results show that this large dataset (which lacks demographic information) can be leveraged together with the preferences of the demographic of interest for a constant number of randomly selected items, to recover an accurate estimate of the entire set of preferences. In this sense, our results can be viewed as a "data prism" allowing one to extract the behavior of specific cohorts from a large, mixed, dataset.
Enumerating Hassett’s Wall and Chamber Decomposition of the Moduli Space of Weighted Stable Curves

Hassett constructed a class of modular compactifications of Mg,n by adding weights to the marked points. This leads to a natural wall and chamber decomposition of the domain of admissible weights D...
Discrete distribution estimation under local privacy

The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed k-ary Randomized Response (k-RR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of k-RR and the existing RAPPOR mechanism at different privacy regimes.
Virtual element methods on meshes with small edges or faces

We consider a model Poisson problem in ℝd (d = 2, 3) and establish error estimates for virtual element methods on polygonal or polyhedral meshes that can contain small edges (d = 2) or small faces ...
On actions of Drinfel'd doubles on finite dimensional algebras

Abstract Let q be an nth root of unity for n > 2 and let T n ( q ) be the Taft (Hopf) algebra of dimension n 2 . In 2001, Susan Montgomery and Hans-Jurgen Schneider classified all non-trivial T n ( q ) -module algebra structures on an n-dimensional associative algebra A. They further showed that each such module structure extends uniquely to make A a module algebra over the Drinfel'd double of T n ( q ) . We explore what it is about the Taft algebras that leads to this uniqueness, by examining actions of (the Drinfel'd double of) Hopf algebras H “close” to the Taft algebras on finite-dimensional algebras analogous to A above. Such Hopf algebras H include the Sweedler (Hopf) algebra of dimension 4, bosonizations of quantum linear spaces, and the Frobenius–Lusztig kernel u q ( sl 2 ) .
Growth of multiplicities of graded families of ideals

Let (R,m) be a Noetherian local ring of dimension d>0. Let I•={In}n∈N be a graded family of m-primary ideals in R. We examine how far off from a polynomial can the length function lR(R/In) be asymptotically. More specifically, we show that there exists a constant γ>0 such that for all n≥0, lR(R/In+1)−lR(R/In)<γnd−1.
Cannon–Thurston maps for hyperbolic free group extensions

This paper gives a detailed analysis of the Cannon{Thurston maps associated to a general class of hyperbolic free group extensions. Let F denote a free groups of nite rank at least 3 and consider a convex cocompact subgroup Out(F), i.e. one for which the orbit map from into the free factor complex of F is a quasi-isometric embedding. The subgroup determines an extension E of F, and the main theorem of Dowdall{Taylor (DT1) states that in this situation E is hyperbolic if and only if is purely atoroidal. Here, we give an explicit geometric description of the Cannon{Thurston maps @F! @E for these hyperbolic free group extensions, the existence of which follows from a general result of Mitra. In particular, we obtain a uniform bound on the multiplicity of the Cannon{Thurston map, showing that this map has multiplicity at most 2 rank(F). This theorem generalizes the main result of Kapovich and Lustig (KL5) which treats the special case where is innite cyclic. We also answer a question of Mahan Mitra by producing an explicit example of a hyperbolic free group extension for which the natural map from the boundary of to the space of laminations of the free group (with the Chabauty topology) is not continuous.
Multi-Level 3D CNN for Learning Multi-Scale Spatial Features

3D object recognition accuracy can be improved by learning the multi-scale spatial features from 3D spatial geometric representations of objects such as point clouds, 3D models, surfaces, and RGB-D data. Current deep learning approaches learn such features either using structured data representations (voxel grids and octrees) or from unstructured representations (graphs and point clouds). Learning features from such structured representations is limited by the restriction on resolution and tree depth while unstructured representations creates a challenge due to non-uniformity among data samples. In this paper, we propose an end-to-end multi-level learning approach on a multi-level voxel grid to overcome these drawbacks. To demonstrate the utility of the proposed multi-level learning, we use a multi-level voxel representation of 3D objects to perform object recognition. The multi-level voxel representation consists of a coarse voxel grid that contains volumetric information of the 3D object. In addition, each voxel in the coarse grid that contains a portion of the object boundary is subdivided into multiple fine-level voxel grids. The performance of our multi-level learning algorithm for object recognition is comparable to dense voxel representations while using significantly lower memory.
Avoiding Scalability Collapse by Restricting Concurrency

Saturated locks often degrade the performance of a multithreaded application, leading to a so-called scalability collapse problem. This problem arises when a growing number of threads circulating through a saturated lock causes the overall application performance to fade or even drop abruptly. This problem is particularly (but not solely) acute on oversubscribed systems (systems with more threads than available hardware cores).
A Carbonic Anhydrase Pseudogene Sensitizes Select Brucella Lineages to Low CO2 Tension.

ABSTRACT Brucella spp. are intracellular pathogens that cause a disease known as brucellosis. Though the genus is highly monomorphic at the genetic level, species have animal host preferences and some defining physiologic characteristics. Of note is the requirement for CO2 supplementation to cultivate particular species, which confounded early efforts to isolate B. abortus from diseased cattle. Differences in the capacity of Brucella species to assimilate CO2 are determined by mutations in the carbonic anhydrase gene, bcaA. Ancestral single-nucleotide insertions in bcaA have resulted in frameshifted pseudogenes in B. abortus and B. ovis lineages, which underlie their inability to grow under the low CO2 tension of a standard atmosphere. Incubation of wild-type B. ovis in air selects for mutations that “rescue” a functional bcaA reading frame, which enables growth under low CO2 and enhances the growth rate under high CO2. Accordingly, we show that heterologous expression of functional Escherichia coli carbonic anhydrases enables B. ovis growth in air. Growth of B. ovis is acutely sensitive to a reduction in CO2 tension, while frame-rescued B. ovis mutants are insensitive to CO2 shifts. B. ovis initiates a gene expression program upon CO2 downshift that resembles the stringent response and results in transcriptional activation of its type IV secretion system. Our study provides evidence that loss-of-function insertion mutations in bcaA sensitize the response of B. ovis and B. abortus to reduced CO2 tension relative to that of other Brucella lineages. CO2-dependent starvation and virulence gene expression programs in these species may influence persistence or transmission in natural hosts. IMPORTANCEBrucella spp. are highly related, but they exhibit differences in animal host preference that must be determined by genome sequence differences. B. ovis and the majority of B. abortus strains require high CO2 tension to be cultivated in vitro and harbor conserved insertional mutations in the carbonic anhydrase gene, bcaA, which underlie this trait. Mutants that grow in a standard atmosphere, first reported nearly a century ago, are easily selected in the laboratory. These mutants harbor varied indel polymorphisms in bcaA that restore its consensus reading frame and rescue its function. Loss of bcaA function has evolved independently in the B. ovis and B. abortus lineages and results in a dramatically increased sensitivity to CO2 limitation.
Online Forecasting of Total-Variation-bounded Sequences

We consider the problem of online forecasting of sequences of length $n$ with total-variation at most $C_n$ using observations contaminated by independent $\sigma$-subgaussian noise. We design an $O(n\log n)$-time algorithm that achieves a cumulative square error of $\tilde{O}(n^{1/3}C_n^{2/3}\sigma^{4/3} + C_n^2)$ with high probability. We also prove a lower bound that matches the upper bound in all parameters (up to a $\log(n)$ factor). To the best of our knowledge, this is the first **polynomial-time** algorithm that achieves the optimal $O(n^{1/3})$ rate in forecasting total variation bounded sequences and the first algorithm that **adapts to unknown** $C_n$.Our proof techniques leverage the special localized structure of Haar wavelet basis and the adaptivity to unknown smoothness parameters in the classical wavelet smoothing [Donoho et al., 1998]. We also compare our model to the rich literature of dynamic regret minimization and nonstationary stochastic optimization, where our problem can be treated as a special case. We show that the workhorse in those settings --- online gradient descent and its variants with a fixed restarting schedule --- are instances of a class of **linear forecasters** that require a suboptimal regret of $\tilde{\Omega}(\sqrt{n})$. This implies that the use of more adaptive algorithms is necessary to obtain the optimal rate.
Numerical solution of scattering problems using a Riemann-Hilbert formulation

A fast and accurate numerical method for the solution of scalar and matrix Wiener-Hopf (WH) problems is presented. The WH problems are formulated as Riemann-Hilbert problems on the real line, and a numerical approach developed for these problems is used. It is shown that the known far-field behaviour of the solutions can be exploited to construct numerical schemes providing spectrally accurate results. A number of scalar and matrix WH problems that generalize the classical Sommerfeld problem of diffraction of plane waves by a semi-infinite plane are solved using the approach.
ON-OFF Privacy with Correlated Requests

We introduce the ON-OFF privacy problem. At each time, the user is interested in the latest message of one of N online sources chosen at random, and his privacy status can be ON or OFF for each request. Only when privacy is ON the user wants to hide the source he is interested in. The problem is to design ON-OFF privacy schemes with maximum download rate that allow the user to obtain privately his requested messages. In many realistic scenarios, the user’s requests are correlated since they depend on his personal attributes such as age, gender, political views, or geographical location. Hence, even when privacy is OFF, he cannot simply reveal his request since this will leak information about his requests when privacy was ON. We study the case when the users’s requests can be modeled by a Markov chain and N = 2 sources. In this case, we propose an ON-OFF privacy scheme and prove its optimality.
A New Look at the “Henry George Theorem”

The Henry George Theorem states that the level of total rents in a country is nearly equal to the total costs of government in that area. There are several unconvincing “proofs” that make this claim. A widely circulated such proof, when inspected closely, is incoherent and unrealistic in its assumptions. Applying the previous chapter’s approach, one can develop a model that shows how rents and the growth of government move together, while allowing for plausible divergences. This suggests that the Henry George Theorem offers a good approach and should figure in policy discussions. An appendix by Andrew Mazzone recalculates rents in the 2016 US National Accounts and shows that redefining rents in a more inclusive manner suggests that rents could come close to financing the costs of government.
Towards Jointly Optimal Placement and Delivery: To Code or Not to Code in Wireless Caching Networks

Coded caching techniques have received significant attention lately due to their provable gains in reducing the cost of data delivery in wireless networks. These gains, however, have only been demonstrated under the assumption of a free placement phase. This unrealistic assumption poses a significant limitation, especially in cases where aggressive placement strategies can lead to a significant transmission cost that may even be higher than the corresponding cost of the delivery phase. In this paper, we relax this assumption and propose a general caching framework that captures the transmission cost of the two phases, and hence, results in minimizing the overall rate of the caching network. We model the dynamic nature of the network through a cost structure that allows for varying the network architecture and cost per transmission, across the placement and delivery phases. We start with the scenario where the individual users have no limit on the available caching memory and characterize the jointly optimal solution as a function of the different parameters in our cost structure. Then, we characterize the effect of memory constraints on the optimal solution in certain special cases. Interestingly, our results identify regions where the uncoded caching scheme outperforms its coded counterpart. Further, coded caching is shown to offer performance gains only when the network architecture during the placement phase is different from that during the delivery phase.
Stochastic grammars for images on arbitrary graphs

We describe a class of multiscale stochastic processes based on stochastic context-free grammars and called spatial random trees (SRTs) which can be effectively used for modeling multidimensional signals. In addition to modeling images which are sampled on a regular rectangular grid, we generalize this methodology to images defined on arbitrary graph structures. We develop likelihood calculation, MAP estimation, and EM-based parameter estimation algorithms for SRTs. To illustrate these methods, we apply them to classification of natural images using region graphs extracted by a recursive bipartitioning segmentation algorithm.
Frequency-domain estimation of multiple access ultra-wideband signals

In a time-hopping ultra-wideband (UWB) system, a receiver is required to operate over a large bandwidth. Conventional receivers consist of sliding correlators to correlate received signal with a template signal. Such a time-domain waveform detection scheme is essentially a single-user detection method, whose performance has been observed to degrade in a multiple access environment. In this paper, estimation of all users' signals is carried out in the frequency domain. First, Fourier transform (FT) is applied to the received time-domain signal. Then users' information in terms of modulation delays is estimated by frequency-domain multiuser detection (MUD) methods. Frequency diversity at the receiver can be explored for performance enhancement by generating multiple sinusoidal waveforms at different frequencies and processing transformed data in parallel. Its promising feature for combating narrow band interference is expected.
Semidefinite programs for exact recovery of a hidden community

We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimation for exactly recovering a hidden community of cardinality $K$ from an $n \times n$ symmetric data matrix $A$, where for distinct indices $i,j$, $A_{ij} \sim P$ if $i, j$ are both in the community and $A_{ij} \sim Q$ otherwise, for two known probability distributions $P$ and $Q$. We identify a sufficient condition and a necessary condition for the success of SDP for the general model. For both the Bernoulli case ($P={\rm Bern}(p)$ and $Q={\rm Bern}(q)$ with $p>q$) and the Gaussian case ($P=\mathcal{N}(\mu,1)$ and $Q=\mathcal{N}(0,1)$ with $\mu>0$), which correspond to the problem of planted dense subgraph recovery and submatrix localization respectively, the general results lead to the following findings: (1) If $K=\omega( n /\log n)$, SDP attains the information-theoretic recovery limits with sharp constants; (2) If $K=\Theta(n/\log n)$, SDP is order-wise optimal, but strictly suboptimal by a constant factor; (3) If $K=o(n/\log n)$ and $K \to \infty$, SDP is order-wise suboptimal. The same critical scaling for $K$ is found to hold, up to constant factors, for the performance of SDP on the stochastic block model of $n$ vertices partitioned into multiple communities of equal size $K$. A key ingredient in the proof of the necessary condition is a construction of a primal feasible solution based on random perturbation of the true cluster matrix.
Characterization of metrizable Esakia spaces via some forbidden configurations

By Priestley duality, each bounded distributive lattice is represented as the lattice of clopen upsets of a Priestley space, and by Esakia duality, each Heyting algebra is represented as the lattice of clopen upsets of an Esakia space. Esakia spaces are those Priestley spaces that satisfy the additional condition that the downset of each clopen is clopen. We show that in the metrizable case Esakia spaces can be singled out by forbidding three simple configurations. Since metrizability yields that the corresponding lattice of clopen upsets is countable, this provides a characterization of countable Heyting algebras. We show that this characterization no longer holds in the uncountable case. Our results have analogues for co-Heyting algebras and bi-Heyting algebras, and they easily generalize to the setting of p-algebras.