Tackles the computational hardness of HPC detection, conjecturing equivalence to PC detection.
problem Computational hardness of hypergraphic planted clique detection.
method No specific method mentioned; focuses on conjecturing equivalence.
result Equivalence of computational hardness between HPC and PC detection.
Study shows challenges in reinforcement learning math problems, proposing enhancements and a hardness measure.
problem Challenges in reinforcement learning finding rare high-reward instances.
method Combining combinatorial group theory, algorithmic enhancements, and topological hardness measure.
result Resolved mathematical questions and proposed enhancements for reinforcement learning.
Study on hard Legendrian unknots using normal rulings.
problem Understanding the complexity of Legendrian unknots in knot theory.
method Using normal rulings to obstruct and construct hard unknot diagrams.
result Construction of infinitely many smoothly hard max-tb unknot diagrams with bounds on minimum possible writhe.
We provide a simpler proof of the hard Lefschetz Theorem for face rings of PL spheres: While the algebraic theory remains the same, we replace the geometric constructions by Pachner's Theorem. This simplifies the reasoning for an important special case of the main result of the first author in arxiv:1812.10454, and alr…
We study the properties of the multiplicative structure on valuations on convex sets. We prove a new version of the hard Lefschetz theorem for even translation invariant continuous valuations, and discuss related problems of integral geometry. Then we formulate a conjectural analogue of this result for odd valuations.
Sparse linear regression is hard to solve efficiently, even with k-sparse solutions.
problem Sparse linear regression problem with k-sparse solutions.
method Fine-grained complexity and hardness assumptions.
result No better-than-brute-force algorithms exist for sparse linear regression.
New findings on maximizing noise stability in partitions of Gaussian space.
problem Maximizing noise stability in partitions of Gaussian space.
method Analyzing the correlation between sets and their noise stability, proving conditional conjectures and hardness results.
result Hyperstable partitions maximize noise stability and have specific properties.
We show that three natural decision problems about links and 3-manifolds are computationally hard, assuming some conjectures in complexity theory. The first problem is determining whether a link in the 3-sphere bounds a Seifert surface with Thurston norm at most a given integer; this is shown to be NP-complete. The sec…
New operators in Khovanov-Rozansky homology exhibit symmetry.
problem Symmetry in Khovanov-Rozansky homology.
method Defined new commuting operators Fk and proved F2 satisfies hard Lefschetz property. result Symmetry in Khovanov-Rozansky homology is confirmed.
Breaks the hardness conjecture for batch RL with a novel tournament-based approach.
problem Sample-efficient reinforcement learning from exploratory data.
method BVFT algorithm using pairwise comparison and state-action partition.
result Solves the learning problem in a setting previously thought impossible.
Paper explores limits of high-order clustering with planted structures.
problem Statistical and computational limits of high-order clustering with planted structures.
method Developed methods for detection and recovery of clusters, identified signal-to-noise ratio boundaries.
result Sharp boundaries of signal-to-noise ratio for statistical and computational feasibility.
New lower bounds for linear classification problems in high dimensions.
problem Linear classification problems in high-dimensional spaces.
method Reduction from hardness conjectures for Affine Degeneracy testing and k-Sum problems.
result Matching lower bounds of Ω(n^d) and respectively Ω(1/ε^d) for Maximum Halfspace Discrepancy problem.
Proves hard Lefschetz theorem and Hodge-Riemann relations for convex valuations.
problem Proving properties of convex valuations analogous to Kähler manifolds.
method Elliptic operator theory and perturbation theory applied to unbounded operators on a Hilbert space.
result Establishes hard Lefschetz theorem and Hodge-Riemann relations for convex bodies.
In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique (PC) con…
New insights link diverse statistical problems via secret leakage planted clique.
problem Statistical-computational gaps in inference problems.
method Secret leakage planted clique as a new hardness assumption for reductions.
result Establishes tight statistical-computational tradeoffs for various problems.
Quantum algorithm approximates Khovanov homology ranks.
problem Efficient computation of Khovanov homology ranks.
method Novel quantum algorithm with pre-thermalization procedure.
result Additive approximations to Khovanov homology ranks are hard problems.
We study (i) asymptotic behaviour of wild harmonic bundles, (ii) the relation between semisimple meromorphic flat connections and wild harmonic bundles, (iii) the relation between wild harmonic bundles and polarized wild pure twistor D-modules. As an application, we show the hard Lefschetz theorem for algebraic semis…
Paper proves computational hardness for graph matching and detection problems.
problem Computational hardness for graph matching and detection problems in correlated random graphs.
method Algorithmic contiguity and low-degree advantage bounds.
result No efficient algorithms exist for certain graph matching and detection problems.
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity -- the second moment of the low-degree likelihood ratio -- gives…
Mathematical Reinforcement Learning faces a 'Two-Hump' problem due to sparse rewards and a scarcity of intermediate 'hard-but-solvable' instances.
problem Mathematical search problems in Reinforcement Learning
method Novel data generation techniques and algorithmic enhancements
result Substantial performance improvements over previous baselines
T. Mochizuki constructs a theory of variations of wild Hodge structure for which the underlying flat connection can have irregular singularities at infinity. He extends in this way the correspondence of Corlette and Simpson between irreducible flat bundles and stables Higgs bundles, taking into account objects with irr…
Quantum circuits are hard to learn on average.
problem Learning the output distributions of quantum circuits is hard.
method Statistical query model analysis.
result Learning quantum circuits requires exponentially many queries.
We construct real polarizable Hodge structures on the reduced leafwise cohomology of Kähler-Riemann foliations by complex manifolds. As in the classical case one obtains a hard Lefschetz theorem for this cohomology. Serre's Kählerian analogue of the Weil conjectures carries over as well. Generalizing a construction of …
New method finds large counterexamples by selectively exploring triangulations.
problem Finding small counterexamples in 3-manifold triangulations. method Selective enumeration of triangulations using heuristics.
result Found counterexamples to three conjectures about vertex triangulations.
Quantum kernels offer potential speed-ups but require encoding problem-specific knowledge.
problem Generalization difficulty in high-dimensional feature spaces.
method Analysis of spectral properties of quantum kernels and their RKHS.
result Quantum advantage is expected if RKHS is low-dimensional and contains hard-to-compute functions.
Consider the Hamiltonian action of a torus on a transversely symplectic foliation that is also Riemannian. When the transverse hard Lefschetz property is satisfied, we establish a foliated version of the Kirwan injectivity theorem, and use it to study Hamiltonian torus actions on transversely Kähler foliations. Among o…
The paper develops L2-Hodge theory on almost Kähler manifolds and proves the Hopf conjecture.
problem Proving the Hopf conjecture for almost Kähler manifolds.
method Developed L2-Hodge theory identities and applied them to prove vanishing theorems and refine estimates. result Proved the Hopf conjecture for compact almost Kähler manifolds with negative sectional curvature.
New results connect RBMs to neural networks, improving learning efficiency.
problem Learning graphical models with latent variables is difficult.
method New connections to learning two-layer neural networks under ℓ∞ bounded input. result Improved algorithm for learning supervised RBMs.
Proves cohomology theorems for tropical varieties.
problem Cohomology of smooth projective tropical varieties.
method Introduces and proves new results in tropical geometry.
result Establishes tropical analogs of three fundamental theorems.
Unified approach to tensor PCA and related problems using tensor cumulants.
problem Statistical inference on invariant distributions, particularly tensor PCA.
method Definition and analysis of tensor cumulants to unify and extend previous results.
result Unified explanation of hardness and subexponential-time algorithms for tensor PCA.
Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
In the present paper we study six dimensional solvable Lie algebras with special emphasis on those admitting a symplectic structure. We list all the symplectic structures that they admit and we compute their Betti numbers finding some properties about the codimension of the nilradical. Next, we consider the conjecture …
Paper proves hardness of learning various complex models under local pseudorandom generators.
problem Hardness of learning various complex models.
method Existence of local pseudorandom generators.
result Proves hardness of learning shallow ReLU neural networks and other models.
This work connects hardness of approximation and learning.
problem Hardness of approximation and learnability in machine learning.
method Shows a single hardness property implying both approximation and learning hardness.
result Obtains new results on hardness of approximation and learnability of specific functions.
Moving between 3-manifold triangulations is NP-hard
problem Moving between two triangulations of a 3-manifold
method Showing that the number of bistellar moves and sparse degree-two edge collapses is NP-hard
result First NP-hardness result concerning moves between two triangulations of a 3-manifold
Researchers use discrete Morse theory to improve the topology of matching complexes of complete graphs.
problem Understanding the topology of matching complexes of complete graphs, especially for small n.
method Developed gradient vector fields to simplify the computation of homology groups.
result Computed the homology groups of M7 efficiently and conjectured an optimal gradient vector field. Hard instances, which require a long time for a specific algorithm to solve, help (1) analyze the algorithm for accelerating it and (2) build a good benchmark for evaluating the performance of algorithms. There exist several efforts for automatic generation of hard instances. For example, evolutionary algorithms have b…
Detecting correlated trees helps align sparse graphs.
problem Detecting correlation between trees for sparse random graphs.
method MPAlign message-passing algorithm for graph alignment.
result MPAlign succeeds in polynomial time for partial alignment.
Three hard diagrams of the unknot require extra crossings to simplify.
problem Finding diagrams of the unknot that require many crossings to simplify.
method Applying previously proposed methods to construct diagrams and using computational resources to prove their hardness.
result Three hard diagrams of the unknot require at least three extra crossings.
Motivated by problems in topology, we explore the complexity of balanced group presentations. We obtain large lower bounds on the complexity of Andrews-Curtis trivialisations, beginning in rank 4. Our results are based on a new understanding of how Dehn functions of groups behave under certain kinds of push-outs. We co…
Study shows Transformers can generalize to varying task lengths.
problem Understanding when and how Transformers can generalize to different input lengths.
method Proposed a unifying framework and introduced the RASP-Generalization Conjecture.
result Transformers tend to length generalize on tasks if solvable by short RASP programs.
Efficient tests achieve best error rates in high-dimensional hypothesis testing.
problem Achieving optimal error rates in computationally efficient hypothesis testing.
method Linear spectral statistics and low-degree likelihood ratio analysis.
result An efficient test achieves the best possible error rates among all computationally efficient tests.
New work shows FP potential monotonicity equals low-degree polynomial estimators limits.
problem Establishing a precise mathematical relationship between statistical physics and polynomial estimators limits.
method Analyzing Gaussian additive models (GAMs) to show FP potential monotonicity equals low-degree polynomial estimators limits.
result For a broad family of Gaussian additive models, the power of low-degree polynomials is equivalent to the monotonicity of the annealed FP potential.
Hardness proven for learning neural networks with polynomial size and Gaussian inputs.
problem Learning one hidden layer ReLU neural networks with polynomial size and Gaussian inputs.
method Based on the hardness of the Continuous Learning with Errors (CLWE) problem.
result Hardness of learning neural networks is proven under standard cryptographic assumptions.
We consider a sparse high dimensional regression model where the goal is to recover a k-sparse unknown vector β∗ from n noisy linear observations of the form Y=Xβ∗+W∈Rn where X∈Rn×p has iid N(0,1) entries and W∈Rn has iid N(0,σ2) entries. Under certa…
A deterministic apple tasting learner is developed, confirming a conjecture and providing tight bounds for mistake bounds.
problem Determining the learnability of hypothesis classes in binary online classification with apple tasting feedback.
method Developed a deterministic apple tasting learner and proved tight bounds for mistake bounds.
result Deterministic apple tasting is feasible and provides tight bounds for mistake bounds.
Study categorizes knots and links as rigid or shaky based on Reidemeister moves.
problem Classifying knots and links as rigid or shaky based on adaptability to Reidemeister moves.
method Categorization of hard diagrams as rigid or shaky, investigation of rigid and shaky hard diagrams for specific knots and links.
result Every link has a rigid hard diagram, and there is an upper limit for the number of crossings in such diagrams.
We describe a method for generating minimal hard prime surface-link diagrams. We extend the known examples of minimal hard prime classical unknot and unlink diagrams up to three components and generate figures of all minimal hard prime surface-unknot and surface-unlink diagrams with prime base surface components up to …