New formula refutes random CSPs with fewer constraints.
problem Refuting random constraint satisfaction problems efficiently.
method Introduced a non-backtracking matrix and proved an Ihara-Bass formula.
result Efficiently refutes random CSPs with fewer constraints.
Study disproves conjecture about low-degree polynomials in hypothesis testing.
problem Conjecture about limitations of polynomial-time algorithms in hypothesis testing.
method Used counterexamples to refute the conjecture and modified the conjecture to rule out the counterexample.
result Disproved conjecture about limitations of low-degree polynomials in hypothesis testing.
Study learning and refutation in non-interactive LDP, showing sample complexity equivalence.
problem Characterize sample complexity for learning and refutation in non-interactive LDP.
method Characterize sample complexity for agnostic PAC learning in non-interactive LDP protocols.
result Optimal sample complexity for any concept class is captured by the approximate γ2~norm of a natural matrix associated with the class. Paper refutes conjecture on tensor power iteration convergence in overcomplete models.
problem Understanding convergence of tensor power iteration in overcomplete random tensors.
method Analysis of tensor power iteration dynamics from random initialization.
result Polynomially many steps are necessary for convergence, refutes logarithmic conjecture.
Study tests five popular trading signal families and finds four refuted, one inconclusive, and one not refuted.
problem Testing the viability of five popular trading signal families for generating a positive edge.
method Statistical edge testing, economic viability assessment, and finite-bankroll survival under leverage using exposure-matched benchmarks, stationary-bootstrap confidence intervals, and hierarchical Benjamini-Yekutieli control.
result Four out of five signal families are refuted, one is inconclusive, and one is not refuted.
Proposes bounds on bias from low-dimensional representations in CATE estimation.
problem Bias in CATE estimation due to low-dimensional representations.
method Proposes a refutation framework to estimate bounds on representation-induced confounding bias.
result Demonstrates effectiveness of refutation framework in practice.
The problem of high-dimensional path-dependent optimal stopping (OS) is important to multiple academic communities and applications. Modern OS tasks often have a large number of decision epochs, and complicated non-Markovian dynamics, making them especially challenging. Standard approaches, often relying on ADP, dualit…
We study dual volume sampling, a method for selecting k columns from an n x m short and wide matrix (n <= k <= m) such that the probability of selection is proportional to the volume spanned by the rows of the induced submatrix. This method was proposed by Avron and Boutsidis (2013), who showed it to be a promising met…
We discuss the mathematician George Bruce Halsted's accusations against Carl Friedrich Gauss, as well as refutations both by the latter's American grandson Robert Gauss in a letter to Felix Klein, and by the historian of mathematics Florian Cajori.
The problem of explaining the behavior of deep neural networks has recently gained a lot of attention. While several attribution methods have been proposed, most come without strong theoretical foundations, which raises questions about their reliability. On the other hand, the literature on cooperative game theory sugg…
Learning the directed acyclic graph (DAG) structure of a Bayesian network from observational data is a notoriously difficult problem for which many hardness results are known. In this paper we propose a provably polynomial-time algorithm for learning sparse Gaussian Bayesian networks with equal noise variance --- a cla…
Gathering the most information by picking the least amount of data is a common task in experimental design or when exploring an unknown environment in reinforcement learning and robotics. A widely used measure for quantifying the information contained in some distribution of interest is its entropy. Greedily minimizing…
New algorithm achieves online calibration in polynomial time for high-dimensional problems.
problem Online calibration of high-dimensional probability distributions over many days.
method Randomly selects among sub-forecasters, each predicting empirical outcome frequency over recent time windows.
result Achieves asymptotically calibrated strategies after polynomial number of rounds, resolving open questions.
For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (ap…
We develop an algorithm of polynomial time complexity to construct the Grushko decomposition of fundamental groups of graphs of free groups with cyclic edge groups. Our methods rely on analysing vertex links of certain CAT(0) square complexes naturally associated with a special class of the above groups. Our main resul…
The paper challenges the notion that asset return doesn't affect Black-Scholes-Merton model.
problem The role of asset return in the Black-Scholes-Merton model.
method Refutation of the claim through simplified stochastic calculus approach.
result The expected rate of return of the underlying asset does affect the Black-Scholes-Merton model.
Dictionary learning is a popular approach for inferring a hidden basis or dictionary in which data has a sparse representation. Data generated from the dictionary A (an n by m matrix, with m > n in the over-complete setting) is given by Y = AX where X is a matrix whose columns have supports chosen from a distribution o…
In the noisy tensor completion problem we observe m entries (whose location is chosen uniformly at random) from an unknown n1×n2×n3 tensor T. We assume that T is entry-wise close to being rank r. Our goal is to fill in its missing entries using as few observations as possible. Let $n = \max(n…
Note refutes examples of Landsberg surfaces with vanishing flag curvature.
problem Verifying examples of Landsberg surfaces with specific curvature properties.
method Analyzing examples from Zhou's result to show they are Berwaldian.
result Examples of Landsberg surfaces with vanishing flag curvature are Berwaldian.
Example shows learnable distributions not privately learnable.
problem Learnable distributions under non-private conditions not transferable to differential privacy.
method Example of a distribution class learnable up to constant error in total variation distance but not under differential privacy.
result Contradicts conjecture of Ashtiani on learnability under differential privacy.
A new knot invariant is fast, strong, topologically meaningful, and fun.
problem Computing and understanding knot invariants efficiently and comprehensively.
method Developed a pair of polynomial knot invariants Θ=(Δ,θ) that are fast, strong, and topologically meaningful.
result Θ is a powerful knot invariant with separation power greater than other known invariants.
Audit shows risk claims from distributional reinforcement learning agents are often false.
problem Evaluating the risk claims made by distributional reinforcement learning agents.
method Combines a decision-relevant screening metric, ground truth from Monte Carlo, and statistical methods to audit risk claims.
result 40-95% of the strongest risk claims are refuted, indicating the learned risk reflects a training artifact rather than environment stochasticity.
Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
Polynomial time algorithm matches correlated Gaussian matrices without vanishing correlation.
problem Matching vertices in two correlated Erdős-Rényi graphs.
method Iterative matching algorithm for correlated Gaussian Wigner matrices.
result First polynomial time algorithm for graph matching with arbitrarily small constant correlation.
Path regularization reveals convex optimization in deep ReLU networks.
problem Understanding the optimization landscape of deep neural networks.
method Introducing path regularization to make the training problem convex and sparsity-inducing.
result Path regularized parallel ReLU networks are a parsimonious convex model in high dimensions.
SAM minimizes loss sharpness, improving adversarial transferability.
problem Improving adversarial transferability of deep neural networks.
method Evaluating surrogate models trained with seven minimizers, focusing on loss sharpness and flat neighborhoods.
result SAM minimizes loss sharpness, leading to better adversarial transferability.
Polynomial-time methods count and sample DAGs from equivalence classes.
problem Counting and sampling DAGs from Markov equivalence classes.
method Polynomial-time algorithms for DAGs.
result Counting and sampling can be done in polynomial time.
We present the strongest known knot invariant that can be computed effectively (in polynomial time).
Investigates polynomial time algorithms for computing Khovanov homology of braids.
problem Computing Khovanov homology for general braids is intractable.
method Examines polynomial time algorithms for 3-braids and a variation of the scanning algorithm for more general braids.
result Shows that for 3-braids, Khovanov homology can be computed in polynomial time, while for more general braids, it can be computed in polynomial time for bounded homological degrees.
Polynomial-time private algorithm for robust estimation of mean and covariance in the presence of outliers.
problem Estimating mean and covariance in the presence of adversarial outliers.
method Stabilizing convex relaxations using a new estimate-dependent noise injection mechanism.
result First efficient private robust estimation algorithm for covariance without condition-number assumptions.
Two new algorithms speed up TreeSHAP computation for tree-based models.
problem Slow computation of SHAP values on tree-based models.
method Two new algorithms, Fast TreeSHAP v1 and v2, designed to improve computational efficiency.
result Fast TreeSHAP v2 is 2.5x faster than TreeSHAP, with slightly higher memory usage.
Making learners robust to adversarial perturbation at test time (i.e., evasion attacks) or training time (i.e., poisoning attacks) has emerged as a challenging task. It is known that for some natural settings, sublinear perturbations in the training phase or the testing phase can drastically decrease the quality of the…
This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002),…
New polynomial-time solutions found for training ReLU networks, mirroring Max-Cut complexity.
problem Training two-layer ReLU neural networks with weight decay regularization.
method Developed a convex formulation and randomized algorithm to find approximate global optimizers.
result First polynomial-time approximation guarantees and hardness of approximation results for regularized ReLU networks.
Polynomial-time methods count and sample DAGs from Markov classes.
problem Counting and sampling Markov equivalent DAGs.
method Polynomial-time algorithms for DAGs from Markov classes.
result Long-standing open problem solved, making practical infeasible strategies feasible.
Coresets are efficient representations of data sets such that models trained on the coreset are provably competitive with models trained on the original data set. As such, they have been successfully used to scale up clustering models such as K-Means and Gaussian mixture models to massive data sets. However, until now,…
Polynomial-time algorithm matches correlated random graphs with non-vanishing correlation.
problem Matching correlated random graphs with non-vanishing edge correlation.
method Iterative algorithm for polynomial-time recovery of latent matching.
result Algorithm succeeds in recovering latent matching as long as edge correlation is non-vanishing.
The generalization of Frobenius' theorem to foliations with singularities is usually attributed to Stefan and Sussmann, for their simultaneous discovery around 1973. However, their result is often referred to without caring much on the precise statement, as some sort of magic spell. This may be explained by the fact th…
We describe a polynomial-time algorithm to compute a (tight) geodesic between two curves in the curve graph. As well as enabling us to compute the distance between a pair of curves, this has several applications to mapping classes. For example, we can use these geodesics to compute the asymptotic translation length, Ni…
In this paper, we develop a new approach to learning high-dimensional Poisson directed acyclic graphical (DAG) models from only observational data without strong assumptions such as faithfulness and strong sparsity. A key component of our method is to decouple the ordering estimation or parent search where the problems…
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.
In this paper we study the adaptive learnability of decision trees of depth at most d from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks $\tilde O(2^…
Polynomial-time algorithm learns causal graphs without parametric assumptions.
problem Learning causal graphs from data without assuming linearity or parametric forms.
method Model-free polynomial-time algorithm with finite-sample guarantees.
result Algorithm achieves linear cost in dimension and samples compared to optimal.
Algorithm classifies surface homeomorphisms with polynomial time complexity.
problem Classifying surface homeomorphisms with polynomial time complexity.
method Algorithm to compute curve distances and decide Nielsen-Thurston types.
result Polynomial time classification of surface homeomorphisms.
The paper proves a conjecture about spacetimes and singularities.
problem Understanding naked singularities and causally simple spacetimes.
method Analyzes null geodesics and spacetime properties to prove conjectures.
result Proves a conjecture about spacetimes and singularities, including implications for two-dimensional spacetimes.
New algorithm recovers sparse measures in polynomial time.
problem Recovering sparse measures from Fourier moments.
method Polynomial-time recovery method inspired by mean-field theory.
result Improves upon convex relaxation methods in specific parameter regime.
New findings on community recovery in SBM with many communities.
problem Determining community recovery conditions in SBM with more than sqrt(n) communities.
method Constructing motifs and counting them to prove community recovery above the proposed threshold.
result Proving community recovery above the proposed threshold in SBM with K >= sqrt(n) communities.
Polynomial-time DP algorithm for learning Gaussians with matching sample complexity.
problem Learning Gaussian distributions while maintaining privacy.
method General framework for reducing DP estimation to non-private, polynomial-time algorithm for Gaussian learning.
result Matching sample complexity to information-theoretic upper bound for Gaussian learning.