Study exact polynomials to compute Mahler measure and relate it to volume function.
problem Compute Mahler measure of exact polynomials.
method Define volume function on vanishing set, prove local extrema on 2D torus, derive Mahler measure formula.
result Prove Mahler measure of irreducible exact polynomials is greater than volume function amplitude.
Algorithm samples from Bingham distribution efficiently.
problem Sampling from the Bingham distribution on a sphere.
method Rejection sampling with polynomial approximation.
result Exact samples from Bingham distribution in polynomial time.
Exact causal network discovery is polynomial for sparse networks.
problem Finding the optimal causal Bayesian network from data is computationally hard.
method Pruning the search space using network properties, combined with dynamic programming and shortest-path searches.
result Exact discovery is polynomial for sparse causal Bayesian networks.
Polynomial representations found in surface braid and mapping class groups.
problem Homological representations of surface braid and mapping class groups.
method Study of homological representation functors and short exact sequences.
result Many homological representation functors are polynomial.
Develops exact convex optimization formulations for neural networks.
problem Training two-layer neural networks with rectified linear units.
method Uses semi-infinite duality and minimum norm regularization to develop exact convex optimization formulations.
result Shows equivalence of ReLU networks trained with weight decay to block ℓ1 penalized convex models. Algorithm for exact partitioning of high-order models using convex tensor relaxation.
problem Exact partitioning of high-order models.
method Defining a general class of m-degree Homogeneous Polynomial Models, relaxing the high-order combinatorial problem to a convex conic form problem, defining the Carathéodory symmetric tensor cone, and constructing a primal-dual certificate. result The solution of the convex relaxation is correct and provides a statistical upper bound for exact partitioning.
EKM solves the K-medoids problem in polynomial time.
problem The K-medoids problem in data analysis. method EKM is a novel algorithm using transformational programming and combinatorial generation.
result EKM solves the K-medoids problem in worst-case $O\left(N^{K+1}
ight)$ time complexity. This paper explains how to compute Khovanov homology of torus links using the Kauffman bracket polynomial.
problem Computing Khovanov homology of specific knot types.
method Categorification of the Kauffman bracket polynomial via a long exact sequence.
result A practical method to compute Khovanov homology of torus links.
Paper develops exact convex optimization for neural networks with polynomial activations.
problem Training two-layer neural networks with nonlinear polynomial activations.
method Exact convex optimization using semidefinite programming.
result Global optimization of neural networks is polynomial-time computable.
Researchers found a new exact solution for pricing Aunt Michaela options using modified Black-Scholes equation.
problem Pricing Aunt Michaela options with a specific maturity condition.
method Computed a new exact series solution of a modified Black-Scholes equation using Maple.
result The modified Black-Scholes equation with Aunt Michaela option is exactly solvable using associated Laguerre polynomials or Whittaker M functions.
Exact formulas for volumes of specific knot cone-manifolds.
problem Finding exact volumes of cone-manifolds with two-bridge knots.
method Provided exact integral formulas using Chebyshev polynomials and algebraic equations.
result Exact formulas for hyperbolic and spherical volumes of cone-manifolds.
For each graph we construct graded cohomology groups whose graded Euler characteristic is the chromatic polynomial of the graph. We show the cohomology groups satisfy a long exact sequence which corresponds to the well-known deletion-contraction rule. This work is motivated by Khovanov's work on categorification of the…
Polynomial-time algorithm for near-optimal community detection in graphs.
problem Node-private community estimation in stochastic block models.
method Explicit Lipschitz surrogate and accept-reject algorithm for sampling community labels.
result Achieves minimax rates for exact recovery with polynomial-time runtime and logarithmic privacy parameter.
New tractable models for complex Ising models over specific topologies.
problem Complex Ising models over specific topologies.
method Sequential application of efficient/inbrute-force inference and sampling to components.
result Improved inference and sampling quality for specific Ising models.
We obtain the first polynomial-time algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown 3-tensor with r incoherent, orthogonal components in Rn from r⋅O~(n1.5) randomly observed entries of the tensor…
Federated learning supports exact support recovery with minimal communication.
problem Learning the exact support of sparse linear regression in federated learning.
method One-shot communication algorithm for exact support recovery without optimization.
result Polynomial sample complexity and logarithmic number of clients required.
To a Legendrian knot, one can associate an A∞ category, the augmentation category. An exact Lagrangian cobordism between two Legendrian knots gives a functor of the augmentation categories of the two knots. We study the functor and establish a long exact sequence relating the corresponding cohomolog…
Polynomial-time reachability for LTI systems with TLL NN controllers is achieved.
problem Bounding the reachable set of LTI systems controlled by TLL NN controllers.
method Polynomial-time computation of exact one-step reachable set and tight bounding box via two methods.
result Exact reachability computation in polynomial time for TLL NN controllers.
Exact minimization of saturated loss functions for robust regression and subspace estimation.
problem Minimizing saturated loss functions for robust regression and subspace estimation.
method Developed an exact algorithm with polynomial time-complexity for robust regression and subspace estimation, relating the problems to linear model approximation.
result Exact minimization of saturated loss functions for robust regression and subspace estimation is possible with polynomial time-complexity.
Paper finds exact recovery threshold in general hypergraph model.
problem Exact recovery of communities in general hypergraph model.
method Developed a two-stage polynomial-time algorithm for exact recovery.
result Sharp threshold for exact recovery in terms of generalized Chernoff-Hellinger divergence.
Efficient algorithm for matching graphs with community structure.
problem Graph matching between correlated stochastic block models with constant correlation.
method Partition trees rooted from each vertex, comparing edge statistics to different communities.
result First low-order polynomial-time algorithm achieving exact matching with high probability in dense graphs.
Develops AMITE for analyzing neural network nonlinearities.
problem Addressing difficulties in verification, explainability, and security in neural network analysis.
method Analytically modified integral transform expansion (AMITE) for neural network nonlinearities.
result First to provide six mutually exclusive desired expansion properties.
The paper confirms Arnold's conjecture about hyperbolic polynomials.
problem The number of connected components of hyperbolic polynomials increases linearly with degree.
method Constructive proof using homotopy invariance of the index of a curve and properties of homogeneous polynomials.
result Exact number of connected components of Hyp(D) is determined and representatives for each component are provided. This paper investigates gradient recovery schemes for data defined on discretized manifolds. The proposed method, parametric polynomial preserving recovery (PPPR), does not require the tangent spaces of the exact manifolds, and they have been assumed for some significant gradient recovery methods in the literature. Ano…
We define several homology theories for central hyperplane arrangements, categorifying well-known polynomial invariants including the characteristic polynomial, Poincare polynomial, and Tutte polynomial. We consider basic algebraic properties of such chain complexes, including long-exact sequences associated to deletio…
We give sharp two-sided linear bounds of the crosscap number (non-orientable genus) of alternating links in terms of their Jones polynomial. Our estimates are often exact and we use them to calculate the crosscap numbers for several infinite families of alternating links and for several alternating knots with up to twe…
Exact inversion of deep ReLU models is possible for single layers and with high probability for deep models.
problem Inverting deep generative models with ReLU activations.
method Theoretical analysis and algorithms for exact inversion of single and multiple layers of deep generative models.
result Exact recovery of latent codes is possible for single layers and with high probability for deep models, under certain conditions.
We analyze how an observer synchronizes to the internal state of a finite-state information source, using the epsilon-machine causal representation. Here, we treat the case of exact synchronization, when it is possible for the observer to synchronize completely after a finite number of observations. The more difficult …
Fairness constraints improve exact recovery in structured prediction models.
problem Exact recovery of fair binary node labels from noisy observations.
method Analyzed Globerson et al. (2015) model with fairness constraints and improved exact recovery for graphs with poor expansion properties.
result Fairness constraints improve the probability of exact recovery from noisy observations.
Proves Vol-Det Conjecture for many alternating links using Mahler measures.
problem Vol-Det Conjecture relating hyperbolic link volumes and determinants.
method Exact computations of Mahler measures of two-variable polynomials.
result Proves Vol-Det Conjecture for many infinite families of alternating links.
Exact Bayesian inference for discrete models using probability generating functions.
problem Discrete statistical models with infinite support and continuous priors.
method Probabilistic programming language with automatic differentiation and probability generating functions.
result Genfer tool provides exact solutions for a wide range of inference problems.
Improved query complexity for adaptive learning of decision trees.
problem Learning decision trees of depth at most d from membership queries.
method Randomized and deterministic polynomial time algorithms with improved query complexity.
result Queries reduced for both randomized and deterministic algorithms.
W. Thurston suggested a method for computing hyperbolic volume of hyperbolic 3-manifolds, based on a triangulation of the manifold. The method was implemented by J. Weeks in the program SnapPea, which produces a decimal approximation as a result. For hyperbolic 2-bridge links, we give formulae that allow one to find th…
The aim of this paper is to state and prove polynomial analogues of the classical Manning inequality relating the topological entropy of a geodesic flow with the growth rate of the volume of balls in the universal covering. To this aim we use two numerical conjugacy invariants, the {\em strong polynomial entropy $h_{po…
Tensor networks speed up Jones polynomial calculation.
problem Efficiently calculating Jones polynomial for complex knots.
method Tensor network contraction for Potts model partition function.
result Jones polynomial can be evaluated subexponentially in knot complexity.
The current article studies certain problems related to complex cycles of holomorphic foliations with singularities in the complex plane. We focus on the case when polynomial differential one-form gives rise to a foliation by Riemann surfaces. In this setting, a complex cycle is defined as a nontrivial element of the f…
AdaPart efficiently samples permanent distributions, improving tracking performance.
problem Computing the permanent of non-negative matrices efficiently.
method AdaPart: simple, efficient method for sampling from unnormalized distributions.
result AdaPart provides tight bounds on the permanent with high probability and polynomial runtime.
Deep polynomial neural networks measure their expressiveness by the dimension of their functional space.
problem Measuring the expressiveness of deep polynomial neural networks.
method Analyzing the algebraic variety defined by the polynomial neural network's weights and activations.
result The dimension of the algebraic variety is a precise measure of the network's expressiveness.
Observational data hints at a finite universe, with spherical manifolds such as the Poincare dodecahedral space tentatively providing the best fit. Simulating the physics of a model universe requires knowing the eigenmodes of the Laplace operator on the space. The present article provides explicit polynomial eigenmodes…
We analyze relations between BPS degeneracies related to Labastida-Marino-Ooguri-Vafa (LMOV) invariants, and algebraic curves associated to knots. We introduce a new class of such curves that we call extremal A-polynomials, discuss their special properties, and determine exact and asymptotic formulas for the correspond…
The paper proposes a method to learn continuous-action graphical games from perturbed equilibria.
problem Learning the exact structure of continuous-action graphical games from limited data.
method A ℓ12− block regularized method to recover the graphical game structure. result The method recovers the exact structure of the graphical game under certain conditions.
We derive a factorization of the Alexander polynomial of the 4-strand Turk's head knot using hypergeometric representations.
problem Deriving a factorization of the Alexander polynomial of the 4-strand Turk's head knot
method Using the reduced Burau representation and multivariable resultant elimination over reciprocal constraints
result Deriving a factorization of the Alexander polynomial in terms of Chebyshev polynomials
In this note, we study the integral of the 1-form logxydy−logyxdx over certain plane curves defined by A-polynomials of knots. It is quite surprising that a Chern-Simons type invariant of 3-manifolds, which can be geometrically computed, may be used to get the exact values of those integrals. Th…
Tests for classifier independence without ground truth labels.
problem Validation of classifier independence without ground truth labels.
method Exact solution for independent binary classifiers using algebraic geometry.
result Self-consistent test for classifier independence without ground truth labels.
New stabilization method in graph braid homology yields polynomial growth.
problem Stabilization in graph braid homology.
method Introduced a stabilization map on graph configuration spaces, leading to a polynomial ring action on homology.
result Homology module is finitely generated and shows polynomial growth in Betti numbers.
Paper resolves bias in ALFT training using generalized alignment games.
problem Systematic bias in estimating logarithmic rewards from small batches.
method Generalized Distributional Alignment Games, U-statistics, minimax polynomial estimators, Variance-Optimal Augmented Polynomial Optimization Program (AQP) Estimator.
result Proves optimal bias and accelerated convergence in ALFT training.
New algorithms explain Naive Bayes classifiers in polynomial time and delay.
problem Computing explanations for Naive Bayes classifiers efficiently.
method Developed log-linear time and polynomial delay algorithms for PI-explanations.
result Efficiently computed PI-explanations for linear classifiers.
Exact universal interpolation property for landmark configurations in Euclidean space.
problem Representing and deforming landmark configurations through flows of vector fields.
method Explicitly describe vector fields for exact universal interpolation property in all dimensions.
result Achieve controllability by combining constant and polynomial vector fields.