The Links-Gould polynomial of alternating knots is shown to be log-concave and positive.
problem Verifying the positivity and log-concavity of the Links-Gould polynomial for alternating knots.
method Formulated a conjecture and verified it computationally for all 51.3 million knots with up to 19 crossings.
result All but 544 knots satisfy a stronger log-concavity condition.
Log-concave coefficient sequences for two-bridge knots proved.
problem Proving log-concavity of Alexander polynomial coefficient sequences for alternating knots.
method Introducing a polynomial Δ ( t ) Δ(t) Δ ( t ) associated to Christoffel words and proving its log-concavity. result Strong Fox conjecture for two-bridge knots proved.
Study proves Alexander polynomials of certain 4-braid knots satisfy a conjecture and gives formulas for log-concave sequences.
problem Proving the Alexander polynomials of certain 4-braid knots satisfy Fox's Trapezoidal Conjecture.
method Analyzes families of alternating 4-braids and n n n -braids, providing explicit formulas and verifying log-concavity. result Explicit formulas for signature and first 4 coefficients of Alexander polynomials, showing log-concavity.
The Links-Gould invariant of alternating links has log-concave coefficients.
problem Log-concavity of Links-Gould coefficients for alternating links.
method Experimental and computational evidence.
result The Links-Gould coefficients of alternating links are log-concave.
We solve a century-old conjecture about Alexander polynomials of special alternating links.
problem Fox's conjecture about unimodality of Alexander polynomial coefficients.
method Proving a multivariate generalization of the Alexander polynomial is Lorentzian.
result Alexander polynomial coefficients of special alternating links form a log-concave sequence.
New algorithms improve convergence rates for non-log-concave sampling and log-partition estimation.
problem Efficiently sampling from non-log-concave distributions and estimating their log-partition function.
method Analysis of information-based complexity, study of polynomial-time sampling algorithms.
result Optimal rates for sampling and log-partition estimation sometimes exceed those for optimization.
New method uses higher-order Langevin dynamics for efficient parallel sampling.
problem Efficient parallel sampling from high-dimensional log-concave distributions.
method Combines higher-order Langevin dynamics with blockwise Lagrange polynomial interpolation.
result Reduces the number of parallel points required for a target accuracy.
Algorithm learns halfspaces with Tsybakov noise in polynomial time.
problem PAC learning halfspaces with adversarial noise.
method Reduction to certifying non-optimality, iterative process, warm-start algorithm.
result First polynomial-time algorithm for learning halfspaces with Tsybakov noise.
New proof of trapezoidal property for Alexander polynomials of special alternating links.
problem Proving trapezoidal property of Alexander polynomials for special alternating links.
method Analyzing vector configurations from matroids and totally positive matrices.
result Alexander polynomials of special alternating links exhibit log-concavity and trapezoidal properties.
The paper studies randomized approximations of Tukey's depth for log-concave isotropic data.
problem The challenge of approximating Tukey's depth in high dimensions.
method The study examines randomized algorithms for approximating Tukey's depth for log-concave isotropic data.
result Randomized algorithms correctly approximate maximal depth and close to zero depths but not intermediate depths.
Gibbs sampler contracts entropy under strong log-concavity, improving mixing time.
problem Improving the mixing time of Gibbs sampler under strong log-concavity.
method Analyzing Gibbs sampler contraction under strong log-concavity, providing sharp contraction rate.
result Gibbs sampler contracts entropy linearly with condition number and independent of dimension under strong log-concavity.
The paper analyzes tensor recovery from symmetric rank-one measurements using information theory.
problem Recovering tensors with low symmetric rank from symmetric rank-one measurements.
method Covering numbers argument, Carbery-Wright inequality, orthogonal polynomials, Fano's inequality.
result Near-optimal sample complexity bounds for log-concave distributions.
Fox's trapezoidal conjecture for four-strand Turk's head knots is proven.
problem Proving log-concavity of the coefficient sequence of D n ( z ) D_n(z) D n ( z ) for four-strand Turk's head knots. method Four-block smoothing theorem for products of reciprocal quartics.
result The coefficient sequence of D n ( z ) D_n(z) D n ( z ) is log-concave. New algorithm samples from log-concave distributions with high accuracy in polynomial time.
problem Sampling from log-concave distributions with high accuracy in infinity distance.
method Directly converts continuous samples from K K K with total-variation bounds to samples with infinity bounds. result Output a point ε ε ε -close to π π π in infinity distance with runtime bounds that depend on polylogarithmic and polynomial factors of 1 / ε 1/ε 1/ ε . We provide new results concerning label efficient, polynomial time, passive and active learning of linear separators. We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a comp…
Polynomial mixing times for simulated tempering in mixture sampling problems.
problem Sampling from mixtures of log-concave distributions with location shifts.
method Conductance decomposition applied to an auxiliary Markov chain on an augmented space.
result First polynomial-time guarantee for simulated tempering with MALA.
Proves tropical Hodge theory for smooth projective varieties, conditional on Laplacian regularity.
problem Proving log-concavity of characteristic polynomials of matroids.
method Combinatorial approach, conditional proof of Kähler package.
result Conditional proof of Kähler package for tropical cohomology.
New sampling method improves efficiency for diffusion models.
problem Efficient sampling from arbitrary smooth distributions in polynomial time.
method Randomized midpoint method for log-concave sampling.
result Achieves best known dimension dependence ( O ~ ( d 5 / 12 ) \widetilde O(d^{5/12}) O ( d 5/12 ) ) for total variation distance. Improved sampling from non-log-concave distributions with polynomial query complexity.
problem Sampling from distributions with non-log-concave densities efficiently.
method Combining Ornstein-Uhlenbeck process assumptions and polynomial moment conditions.
result Polynomial query complexity improvement over previous methods.
We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider both the malicious noise model and the adversarial label nois…
Efficient algorithm for learning halfspaces in a new model with polynomial time complexity.
problem Learning halfspaces in the testable learning model with distributional constraints.
method Developed new tests using labels and combined with moment-matching approach.
result Achieved near optimal error rates for Gaussian and strongly log-concave distributions.
Paper tackles sampling from non-log-concave distributions using denoising diffusion.
problem Sampling from non-log-concave distributions efficiently.
method DDMC framework, Zeroth-Order Diffusion Monte Carlo (ZOD-MC) algorithm.
result ZOD-MC achieves inverse polynomial dependence on sampling accuracy, efficient for low dimensions.
Universal tester-learner for halfspaces over structured distributions.
problem Learning halfspaces over a wide class of structured distributions.
method Uses a fully polynomial tester-learner based on hypercontractivity and sum-of-squares (SOS) programs.
result Achieves error O ( o p t ) + ε O(\mathrm{opt}) + ε O ( opt ) + ε on any labeled distribution that the tester accepts. Proves log-concavity of cluster algebra coefficients for type A n A_n A n .
problem Log-concavity of cluster algebra coefficients.
method Introduced atomic theta basis and proved log-concavity for type A n A_n A n . result Proved log-concavity of coefficients for cluster algebra variables of type A n A_n A n . Study improves sampling from non-log-concave distributions using Fisher information.
problem Sampling from non-log-concave distributions with high Fisher information guarantees.
method Proximal sampler with RGO implementation, leveraging log-concave sampling results.
result Improved complexity guarantee in relative Fisher information for non-log-concave sampling.
Paper reduces sample complexity for bilinear systems identification to nearly constant.
problem Identifying discrete-time bilinear systems under bounded disturbances.
method Uses trajectory-dependent regressors and polynomial mean-square state growth analysis.
result Proves sample complexity of O ~ ( 1 / ε ) \widetilde{\mathcal O}(1/ε) O ( 1/ ε ) for estimation error ε ε ε . Establishes log-concavity estimates for convex domains' first Dirichlet eigenfunctions.
problem Quantifying the Hessian of log-concave eigenfunctions on convex domains.
method Analyzes log-concavity properties of the first Dirichlet eigenfunction on convex domains.
result Obtains quantitative estimates for the Hessian of log u \log u log u . New sampling algorithm for non-log-concave distributions requires many queries.
problem Sampling from non-log-concave distributions with good accuracy.
method Lower bound on query complexity and algorithm for sampling.
result Tight query complexity characterization for sampling from non-log-concave distributions.
Algorithm learns halfspaces in noisy data efficiently.
problem Learning halfspaces with Tsybakov noise.
method Novel semi-definite programming and online convex optimization.
result First non-trivial PAC learning algorithm for Tsybakov noise.
Log-concavity of eigenfunctions on curved surfaces is proven, leading to fundamental gap estimates.
problem Proving log-concavity of eigenfunctions on curved surfaces.
method Analyzing the Laplacian eigenfunctions on positively curved surfaces.
result Strong log-concavity of the first eigenfunction on positively curved surfaces.
A key task in Bayesian statistics is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). However, without any assumptions, sampling (even approximately) can be #P-hard, and few works have provided "beyond worst-case" guarantees for such settings. For log-c…
Improved sampling guarantees for weakly log-concave distributions.
problem Sampling from distributions that are not strongly log-concave.
method Proximal sampler with convergence guarantees under weaker assumptions.
result New state-of-the-art sampling guarantees for various target distributions.
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.
Log-concavity proven for multinomial likelihoods under specific constraints.
problem Log-concavity of multinomial likelihoods under interval censoring constraints.
method Proved log-concavity by showing M-convex subsets of the discrete simplex.
result Likelihood function is completely log-concave.
Introduces CSLC models to bridge deep generative models and classical algorithms.
problem Mode collapse and memorization issues in deep generative models and restrictive assumptions in classical algorithms.
method Introduces conditionally strongly log-concave (CSLC) models, factorizing data distribution into strongly log-concave conditional distributions.
result Efficient parameter estimation and sampling algorithms with theoretical guarantees for non-log-concave data distributions.
In many applications, data is collected in batches, some of which are corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating discrete distributions in this setting. We consider a general framework of robust learning from batches, and determine the limits of both classification and dis…
New method samples from non-log-concave distributions with weak dissipativity.
problem Sampling from distributions that are not log-concave and weakly dissipative.
method Taming scheme tailored to growth and decay properties of the target distribution.
result Explicit non-asymptotic guarantees for KL, TV, and Wasserstein distances.
Estimates log-concave densities in graphical models using tent functions.
problem Maximum likelihood estimation of log-concave densities in undirected graphs.
method MLE as product of tent functions corresponding to maximal cliques.
result MLE can be found via convex optimization.
New bounds for SMC show its advantage over MCMC in multimodal distributions.
problem Estimating expectations under multimodal distributions with slow global mixing.
method Proves finite sample complexities for SMC with local mixing times, addressing bias through sequential resampling.
result SMC provides fully polynomial time approximation for multimodal problems.
Paper proves super log-concavity of first eigenfunction for certain hyperbolic domains.
problem Proving super log-concavity of first eigenfunction for horo-convex domains in hyperbolic space.
method Analyzes properties of Laplacian eigenfunctions in hyperbolic geometry.
result Optimal proof of super log-concavity for horo-convex domains with constraints.
The paper develops inequalities for log-concave functions and related surface areas.
problem Understanding log-concave functions and their inequalities.
method Establishing new inequalities through f-divergences and functional affine surface areas.
result New inequalities on functional affine surface area and bounds for Kullback-Leibler divergence.
We construct a compact symplectic manifold with a Hamiltonian circle action for which the Duistermaat-Heckman function is not log-concave.
CAVI converges for log-concave measures via optimal transport.
problem Finding the closest product measure to a log-concave measure via CAVI.
method Adapting coordinate descent techniques from Euclidean space to optimal transport for log-concave densities.
result Proves convergence of CAVI for log-concave densities and provides rates of convergence under additional conditions.
Zigzag sampling algorithm efficiently samples from strongly log-concave distributions with low computational cost.
problem Sampling from strongly log-concave distributions efficiently and with low computational complexity.
method Zigzag sampling algorithm with warm start assumption, focusing on gradient evaluations.
result Achieves ε error in chi-square divergence with computational cost of O(κ²d^(1/2)(log(1/ε))^(3/2)) gradient evaluations.
A new method simplifies sampling from complex distributions without using diffusions.
problem Sampling from complex, high-dimensional distributions efficiently.
method Reduces sampling to solving a sequence of 'nice' sampling problems using SLC distributions.
result Shows how to traverse backwards paths using high-accuracy routines for SLC distributions.
New lower bounds for sampling from log-concave distributions in higher dimensions.
problem Proving lower bounds for sampling from log-concave distributions in higher dimensions.
method Multiscale construction inspired by geometric measure theory and reduction to block Krylov algorithms.
result Query lower bounds for sampling from log-concave distributions in higher dimensions are established.
Study Langevin Monte Carlo for sampling non-log-concave distributions.
problem Sampling from non-log-concave distributions, especially Gaussian mixtures.
method Discretizations of overdamped Langevin diffusions.
result Numerical simulations compare Langevin Monte Carlo algorithms' performance.
Karshon constructed the first counterexample to the log-concavity conjecture for the Duistermaat-Heckman measure: a Hamiltonian six manifold whose fixed points set is the disjoint union of two copies of T 4 T^4 T 4 . In this article, for any closed symplectic four manifold N N N with b + b+ b + greater than 1, we show that there is a…