A threshold κ=Θ(1/√α) (α=m/n) separates easy collision finding from OGP-based exponential lower bounds against online algorithms in single-layer binary NNs.
hub
Comput.54, 2 (2025), 193–232
27 Pith papers cite this work. Polarity classification is still indexing.
27
Pith papers citing it
hub tools
citation-role summary
method 3
background 1
citation-polarity summary
representative citing papers
Minimax sample complexity for uniform L_infty estimation is Theta(n^{d+1}) for degree-d polynomials and Theta(ns^2) for s-sparse Fourier-Walsh polynomials under noise, exceeding noiseless rates by factors of n and s.
Establishes statistical and computational optimality thresholds for common subspace estimation and inference under varying SNR regimes, including an impossibility result for adaptive confidence intervals below strong inference SNR.
SASA replaces single-vector decoders in SAEs with learned subspaces plus block sparsity and nuclear-norm regularization, proving that a single group becomes the global minimizer once block size meets intrinsic dimension and yielding polynomial rather than exponential sample complexity.
A Gaussian mean width bound in weighted geometry yields a single-letter strong converse for the classical identification capacity of quantum channels, improving known results for depolarizing, Pauli, erasure, and amplitude damping channels.
Introduces a TAP-motivated framework and constructs explicit parameter-free spectral algorithms that achieve strong detection and weak recovery thresholds in three canonical correlated two-view models with matching lower bounds.
Random fields destroy phase transitions in low-dimensional Widom-Rowlinson models but preserve them in high dimensions for large densities.
The test error of random-feature ridge regression with arbitrary data augmentation admits a closed-form asymptotic characterization in the proportional regime that depends only on population covariances and augmentation statistics.
The Sinkhorn treatment effect is a new entropic optimal transport measure of divergence between counterfactual distributions that admits first- and second-order pathwise differentiability, debiased estimators, and asymptotically valid tests for distributional treatment effects.
PUICL is a transformer pretrained on synthetic PU data from structural causal models that solves positive-unlabeled classification via in-context learning without gradient updates or fitting.
Decomposes excess risk in nonstationary weighted ERM into learning and drift terms, then proves oracle inequalities under mixing that recover minimax rates in stationary cases.
Generalized entanglement entropies are constructed via left-, right-, and bi-invariant unit-invariant singular value decompositions to ensure scale invariance for non-Hermitian and rectangular operators in quantum mechanics, random matrices, and Chern-Simons theory.
Proposes ERHT-CC test based on spatial median and spatial-sign covariance with Cauchy aggregation over ridge parameters, deriving asymptotic normality and local power under elliptical symmetry.
Defines saturation index S(K) = erank(Σ̂_W^(K))/K that identifies when linear discriminant stabilizes in binary few-shot classification, with empirical phase diagram and stopping-rule AUC of 0.752 on 17 tasks.
Characterizes duals of white-noise-driven continuous stochastic flows by explicit SDEs and introduces a self-dual polynomially self-repelling flow model.
Wasserstein least squares extends Euclidean least squares to distribution-valued responses via convex analysis, yielding n^{-1/2} rates under template deformation and faster barycenter rates than prior work.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
Perturb-and-Correct generates epistemically diverse predictors from a single pretrained network via hidden-layer perturbations followed by affine least-squares corrections that enforce agreement on calibration data.
Resolvents of the sample covariances in the separable mixture model approximate deterministic matrices defined via solutions to a dual system of equations, without simultaneous diagonalizability assumptions.
Dynamic directed spectral co-clustering on degree-corrected stochastic co-blockmodels embedded in VAR-type models uncovers latent community paths, with non-asymptotic misclassification bounds and applications to U.S. payrolls and global stock volatilities.
A new framework combines AI-derived concept embeddings with high-dimensional selective inference to enable statistically principled, interpretable discovery from unstructured data in empirical economics.
Gaussian randomized rounding on two-qubit marginals of depth-D circuits with local depolarizing noise p yields samples whose expected Max-Cut cost matches the noisy quantum device up to an approximation ratio of 1-O[(1-p)^D].
Proves approximate Gaussianity of debiased linear forms of eigenvectors in matrix denoising and spiked PCA models under Gaussian noise, then constructs bias/variance estimators yielding minimax-optimal confidence intervals without sample splitting.
An optimal transport method is proposed to construct confidence intervals with improved coverage, including theoretical consistency results, error bounds, and simulation comparisons.
citing papers explorer
-
Collision Resistance of Single-Layer Neural Nets
A threshold κ=Θ(1/√α) (α=m/n) separates easy collision finding from OGP-based exponential lower bounds against online algorithms in single-layer binary NNs.
-
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Minimax sample complexity for uniform L_infty estimation is Theta(n^{d+1}) for degree-d polynomials and Theta(ns^2) for s-sparse Fourier-Walsh polynomials under noise, exceeding noiseless rates by factors of n and s.
-
Statistically and Computationally Optimal Estimation and Inference of Common Subspaces
Establishes statistical and computational optimality thresholds for common subspace estimation and inference under varying SNR regimes, including an impossibility result for adaptive confidence intervals below strong inference SNR.
-
Subspace-Aware Sparse Autoencoders for Effective Mechanistic Interpretability
SASA replaces single-vector decoders in SAEs with learned subspaces plus block sparsity and nuclear-norm regularization, proving that a single group becomes the global minimizer once block size meets intrinsic dimension and yielding polynomial rather than exponential sample complexity.
-
Gaussian mean width strong converse bound on the classical identification capacity of quantum channels
A Gaussian mean width bound in weighted geometry yields a single-letter strong converse for the classical identification capacity of quantum channels, improving known results for depolarizing, Pauli, erasure, and amplitude damping channels.
-
Optimal Spectral Algorithms for Correlated Two-view Models in High Dimensions
Introduces a TAP-motivated framework and constructs explicit parameter-free spectral algorithms that achieve strong detection and weak recovery thresholds in three canonical correlated two-view models with matching lower bounds.
-
Lattice random-field Widom--Rowlinson models
Random fields destroy phase transitions in low-dimensional Widom-Rowlinson models but preserve them in high dimensions for large densities.
-
Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation
The test error of random-feature ridge regression with arbitrary data augmentation admits a closed-form asymptotic characterization in the proportional regime that depends only on population covariances and augmentation statistics.
-
Sinkhorn Treatment Effects: A Causal Optimal Transport Measure
The Sinkhorn treatment effect is a new entropic optimal transport measure of divergence between counterfactual distributions that admits first- and second-order pathwise differentiability, debiased estimators, and asymptotically valid tests for distributional treatment effects.
-
In-Context Positive-Unlabeled Learning
PUICL is a transformer pretrained on synthetic PU data from structural causal models that solves positive-unlabeled classification via in-context learning without gradient updates or fitting.
-
Fast Rates for Nonstationary Weighted Risk Minimization
Decomposes excess risk in nonstationary weighted ERM into learning and drift terms, then proves oracle inequalities under mixing that recover minimax rates in stationary cases.
-
Generalised Entanglement Entropies from Unit-Invariant Singular Value Decomposition
Generalized entanglement entropies are constructed via left-, right-, and bi-invariant unit-invariant singular value decompositions to ensure scale invariance for non-Hermitian and rectangular operators in quantum mechanics, random matrices, and Chern-Simons theory.
-
Elliptical Regularized Hotelling Testing for High Dimensional Data
Proposes ERHT-CC test based on spatial median and spatial-sign covariance with Cauchy aggregation over ridge parameters, deriving asymptotic normality and local power under elliptical symmetry.
-
A Spectral Phase Diagram for Binary Few-Shot Classification: Intrinsic Dimensionality, Geometric Saturation, and Representational Diagnosis
Defines saturation index S(K) = erank(Σ̂_W^(K))/K that identifies when linear discriminant stabilizes in binary few-shot classification, with empirical phase diagram and stopping-rule AUC of 0.752 on 17 tasks.
-
Continuous stochastic flows driven by white noise and their duals
Characterizes duals of white-noise-driven continuous stochastic flows by explicit SDEs and introduces a self-dual polynomially self-repelling flow model.
-
Wasserstein Least Squares: A Canonical Regression Method for Probability Distributions
Wasserstein least squares extends Euclidean least squares to distribution-valued responses via convex analysis, yielding n^{-1/2} rates under template deformation and faster barycenter rates than prior work.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
-
Perturb and Correct: Post-Hoc Ensembles using Affine Redundancy
Perturb-and-Correct generates epistemically diverse predictors from a single pretrained network via hidden-layer perturbations followed by affine least-squares corrections that enforce agreement on calibration data.
-
Spectral approximation for the separable covariance mixture model
Resolvents of the sample covariances in the separable mixture model approximate deterministic matrices defined via solutions to a dual system of equations, without simultaneous diagonalizability assumptions.
-
Latent community paths in VAR-type models via dynamic directed spectral co-clustering
Dynamic directed spectral co-clustering on degree-corrected stochastic co-blockmodels embedded in VAR-type models uncovers latent community paths, with non-asymptotic misclassification bounds and applications to U.S. payrolls and global stock volatilities.
-
Making Interpretable Discoveries from Unstructured Data: A High-Dimensional Multiple Hypothesis Testing Approach
A new framework combines AI-derived concept embeddings with high-dimensional selective inference to enable statistically principled, interpretable discovery from unstructured data in empirical economics.
-
Sampling (noisy) quantum circuits through randomized rounding
Gaussian randomized rounding on two-qubit marginals of depth-D circuits with local depolarizing noise p yields samples whose expected Max-Cut cost matches the noisy quantum device up to an approximation ratio of 1-O[(1-p)^D].
-
Statistical Inference for Linear Functions of Eigenvectors with Small Eigengaps
Proves approximate Gaussianity of debiased linear forms of eigenvectors in matrix denoising and spiked PCA models under Gaussian noise, then constructs bias/variance estimators yielding minimax-optimal confidence intervals without sample splitting.
-
An Optimal Transportation Approach for Improved Confidence Intervals
An optimal transport method is proposed to construct confidence intervals with improved coverage, including theoretical consistency results, error bounds, and simulation comparisons.
-
Generalization of Zeroth-Order Method for Quotients of Quadratic Functions
A generalized zeroth-order method samples random directions on the sphere to optimize quotients of quadratics, estimates Riemannian derivatives with surrogates, and yields an accelerated algorithm outperforming prior work.
-
Entanglement and circuit complexity in finite-depth random linear optical networks
In finite-depth random linear optical circuits, entanglement grows at most diffusively and robust circuit complexity scales similarly, with depth bounds ensuring near-maximal subsystem entanglement and closeness to Haar unitaries.
-
Multi-Dimensional Matching in Market Design
Proposes SVD-based reduction of multi-dimensional matching to 1D problem for O(N log N) computation that approximates Nash Social Welfare under low effective dimensionality.