Combinatorial modifications of Reeb graphs and the realization problem
November 19, 2018
Mathematics
Geometric Topology
We prove that, up to homeomorphism, any graph subject to natural necessary
conditions on orientation and the cycle rank can be realized as the Reeb graph
of a Morse function on a given closed manifold M. Along the way, we show that
the Re...
Unifying lower bounds for algebraic machines, semantically
November 16, 2018
| |
Computer Science
Computational Complexity
Logic in Computer Science
This paper presents a new abstract method for proving lower bounds in
computational complexity. Based on the notion of topological and measurable
entropy for dynamical systems, it is shown to generalise three previous lower
bounds results f...
A Spectral View of Adversarially Robust Features
November 15, 2018
| | |
Computer Science
Statistics
Machine Learning
Machine Learning
Given the apparent difficulty of learning models that are robust to
adversarial perturbations, we propose tackling the simpler problem of
developing adversarially robust features. Specifically, given a dataset and
metric of interest, the go...
Incentivizing Exploration with Selective Data Disclosure
November 14, 2018
| | |
Computer Science
Computer Science and Game Theory
Data Structures and Algorithms
Machine Learning
We propose and design recommendation systems that incentivize efficient
exploration. Agents arrive sequentially, choose actions and receive rewards,
drawn from fixed but unknown action-specific distributions. The recommendation
system prese...
Universal Polarization for Processes with Memory
November 14, 2018
|
Computer Science
Mathematics
Information Theory
Information Theory
A transform that is universally polarizing over a set of channels with memory
is presented. Memory may be present in both the input to the channel and the
channel itself. Both the encoder and the decoder are aware of the input
distribution,...
Factoring Non-negative Operator Valued Trigonometric Polynomials in Two
Variables
November 14, 2018
|
Mathematics
Functional Analysis
Functional Analysis
It is shown using Schur complement techniques that on finite dimensional
Hilbert spaces, a non-negative operator valued trigonometric polynomial in two
variables with degree (d1,d2) can be written as a finite sum of hermitian
squares of...
Geometry of Gaussian free field sign clusters and random interlacements
November 14, 2018
| |
Mathematics
Physics
Probability
Mathematical Physics
Mathematical Physics
For a large class of amenable transient weighted graphs G, we prove that
the sign clusters of the Gaussian free field on G fall into a regime of
strong supercriticality, in which two infinite sign clusters dominate (one for
each sign), ...
Thermopower in an anisotropic two-dimensional Weyl semimetal
November 12, 2018
|
Physics
Mesoscale and Nanoscale Physics
Strongly Correlated Electrons
We investigate the generation of an electric current from a temperature
gradient in a two-dimensional Weyl semimetal with anisotropy, in both the
presence and absence of a quantizing magnetic field. We show that the
anisotropy leads to dopi...
When Locally Linear Embedding Hits Boundary
November 11, 2018
|
Mathematics
Statistics
Statistics Theory
Statistics Theory
Based on the Riemannian manifold model, we study the asymptotic behavior of a
widely applied unsupervised learning algorithm, locally linear embedding (LLE),
when the point cloud is sampled from a compact, smooth manifold with boundary.
We ...
Weak convergence of particle swarm optimization
November 10, 2018
| |
Mathematics
Probability
Particle swarm optimization algorithm is a stochastic meta-heuristic solving
global optimization problems appreciated for its efficacity and simplicity. It
consists in a swarm of particles interacting among themselves and searching the
glob...