Computing unlinking number is usually very difficult and complex problem, therefore we define BJ-unlinking number and recall Bernhard-Jablan conjecture stating that the classical unknotting/unlinking number is equal to the BJ-unlinking number. We compute BJ-unlinking number for various families of knots and links for w…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “computational gaps”
Researchers compute gap distributions for saddle connection directions on specific translation surfaces.
problem Computing gap distributions for saddle connection directions on translation surfaces.
method Translation to dynamical question of return times to a transversal under the horocycle flow.
result Gap distributions have support at 0 and quadratic tail decay.
Noise Sensitivity Exponent controls statistical-computational gaps in learning.
problem Understanding when learning is statistically possible yet computationally hard in high-dimensional statistics.
method Investigating statistical-computational gaps in single- and multi-index models using Noise Sensitivity Exponent.
result Noise Sensitivity Exponent governs statistical-computational gaps in high-dimensional learning.
Data visualization and interaction with large data sets is known to be essential and critical in many businesses today, and the same applies to research and teaching, in this case, when exploring large and complex mathematical objects. GAP is a computer algebra system for computational discrete algebra with an emphasis…
simpcomp is an extension (a so called package) to GAP, the well known system for computational discrete algebra. The package enables the user to compute numerous properties of (abstract) simplicial complexes, provides functions to construct new complexes from existing ones and an extensive library of triangulations of …
Statistical-computational gap found in aligning multiple Gaussian graphs.
problem Aligning multiple Gaussian graphs with unknown signals.
method Generalized informational threshold and computational barrier analysis.
result Existence of a statistical-computational gap in multiple Gaussian graph alignment.
Study potential computational gaps in symmetric binary perceptrons using fl-RDT.
problem Potential statistical-computational gaps in symmetric binary perceptrons.
method Parametric utilization of fully lifted random duality theory (fl-RDT).
result Observation of a computational gap in SBP.
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
We explicitly compute the limiting gap distribution for slopes of saddle connections on the flat surface associated to the regular octagon with opposite sides identified. This is the first such computation where the Veech group of the translation surface has multiple cusps. We also show how to parametrize a Poincaré se…
Study spectral gaps in hyperbolic rational homology spheres.
problem Finding spectral gaps in hyperbolic rational homology spheres.
method Construction of families of hyperbolic rational homology spheres with coexact 1-form spectral gaps.
result Provided intervals containing limit points of spectral gaps, with the rightmost interval being [0.8196, 0.8277].
We give an explicit formula for the limiting gap distribution of slopes of saddle connections on the golden L, or any translation surface in its SL(2, R)-orbit, in particular the double pentagon. This is the first explicit computation of the distribution of gaps for a flat surface that is not a torus cover.
A generalization gap estimation for overparameterized models via the Langevin functional variancestat.ML
Estimates generalization gap for overparameterized models using Langevin approximation.
problem Estimating the difference between training and generalization performance in overparameterized models.
method Functional variance and Langevin approximation of functional variance.
result Demonstrates efficient estimation of generalization gaps for overparameterized models.
Study calculates eigenvalues and eigenfunctions for spherical triangles and finds fundamental gap behavior.
problem Understanding eigenvalues and gaps in spherical triangles.
method Explicit computation of Dirichlet eigenvalues and eigenfunctions for spherical lunes and triangles.
result Fundamental gap of spherical triangles increases as the angle of the lune decreases.
Slope gap distribution of the double heptagon and an algorithm for determining winning vectorsmath.DS
The paper calculates gap distributions for translation surfaces, focusing on the double heptagon.
problem Calculating gap distributions for translation surfaces.
method Describes a procedure to find winning holonomy vectors and applies it to the double heptagon.
result Explicitly computed gap distribution for the regular double heptagon translation surface.
Study calculates slope gaps on polygon surfaces, finding non-unimodal distributions.
problem Understanding the distribution of slope gaps on polygon surfaces.
method Explicit computation of slope gap distributions for 2n-gons, providing bounds on non-differentiability points.
result Slope gap distributions are not always unimodal, answering a question by Athreya.
Formula found for surfaces in Sol_3, leading to gap results.
problem Finding constant mean curvature surfaces in Sol_3.
method Computed Laplacian of squared norm of second fundamental form, used Simons type formula.
result Gap results for compact constant mean curvature surfaces.
Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non-dedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are i…
A new method is proposed to compute connectivity measures on multivariate time series with gaps. Rather than removing or filling the gaps, the rows of the joint data matrix containing empty entries are removed and the calculations are done on the remainder matrix. The method, called measure adapted gap removal (MAGR), …
New method explains computational barriers in high-dimensional statistical models.
problem Understanding detection-recovery gaps in high-dimensional inference.
method Combining algorithmic contiguity and cross-validation reduction to obtain conditional computational lower bounds.
result Mild control of low-degree advantage is sufficient to explain computational barriers for recovery.
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
There is a gap in the proof of the main theorem in the article [ShCh13a] on optimal bounds for the Morse lemma in Gromov-hyperbolic spaces. We correct this gap, showing that the main theorem of [ShCh13a] is correct. We also describe a computer certification of this result.
A new screening test for Lasso improves solution speed.
problem Improving the efficiency of Lasso solution methods.
method Safe region with dome geometry based on dual cutting half-spaces.
result The new screening test leads to significant acceleration.
We give a new lower bound for the first gap of the Dirichlet eigenvalues of the Schr{ö}dinger operator on a bounded convex domain in R or S and greatly sharpens the previous estimates. The new bound is explicit and computable.
The study improves fundamental gap estimates for surfaces with non-constant positive curvature.
problem Estimating the fundamental gap for surfaces with non-constant positive curvature.
method Using a two-point maximum principle, the study establishes log-concavity and fundamental gap estimates.
result Corresponding log-concavity and fundamental gap estimates for surfaces with non-constant positive curvature are derived.
New curvature measure defined for graphs, with bounds on diameter and spectral gap.
problem Defining curvature for graphs and proving its properties.
method Solving linear systems to compute curvature; applying minimax theorem.
result Graphs with positive curvature have bounded diameter and spectral gap.
Detection of dense cycles in graphs reveals a gap between easy detection and hard recovery.
problem Detecting and recovering dense cycles in Erdős-Rényi graphs.
method Characterization of computational thresholds for detection and recovery using low-degree polynomial algorithms.
result A gap exists between the detection and recovery thresholds for certain parameter regimes.
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances…
Study shows computational and statistical gaps in Gaussian Single-Index Models.
problem Statistical and computational trade-offs in high-dimensional regression problems.
method Analysis of SQ and LDP frameworks, partial-trace algorithm.
result Computational algorithms require significantly more samples than information-theoretic limits.
Privacy improves robustness in statistical estimation.
problem Sparse mean estimation under privacy constraints.
method Sum-of-Squares method and exponential-time mechanisms.
result Private algorithms matching optimal tradeoffs are not known, but achieved via Sum-of-Squares.
New study shows limits of low-degree algorithms in finding large independent sets in sparse hypergraphs.
problem Finding large independent sets in sparse random hypergraphs.
method Low-degree polynomial algorithms are analyzed to determine their limits.
result Low-degree algorithms can find independent sets of density up to \(\left(\frac{\log d}{(r-1)d}
ight)^{1/(r-1)}\), but no larger.
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gapsstat.ML
Lasso performs poorly with correlated covariates, but a rescaled approach fixes this.
problem Lasso's performance degrades with correlated covariates, leading to inefficiency.
method Proposes a rescaling method for Lasso to handle correlated covariates effectively.
result Rescaled Lasso provides strong provable guarantees for estimation with quadratic sample complexity.
We consider the weakly supervised binary classification problem where the labels are randomly flipped with probability . Although there exist numerous algorithms for this problem, it remains theoretically unexplored how the statistical accuracies and computational efficiency of these algorithms depend on the degr…
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversariescs.CC
This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detection-recovery gap and a universality principle for these gaps. A main feature of our approach is to ma…
New framework tightens certified robustness gaps in machine learning models.
problem Persistent gap between theoretical certified robustness and empirical accuracy.
method Leverages Lipschitz continuity and novel confidence intervals.
result Improves robust accuracy, compressing the gap between theory and practice.
Price gap, defined as the logarithmic price difference between the first two occupied price levels on the same side of a limit order book (LOB), is a key determinant of market depth, which is one of the dimensions of liquidity. However, the properties of price gaps have not been thoroughly studied due to the less avail…
Chaos in cerebellar cells enhances complexity of neural patterns.
problem Understanding how cerebellar granular layer represents complex information.
method Constructed a model of cerebellar granular layer with gap junctions, evaluated using reservoir computing.
result Chaotic dynamics in the cerebellar granular layer produce complex and diverse output patterns.
This work analyzes the gap between off-policy and on-policy policy gradient methods and provides conditions to reduce this gap.
problem The gap between off-policy and on-policy policy gradient methods and conditions to reduce it.
method Theoretical analysis and empirical evidence of conditions to reduce the on-off gap.
result Conditions to reduce the on-off gap between off-policy and on-policy policy gradient methods.
In high dimensional settings, sparse structures are crucial for efficiency, either in term of memory, computation or performance. In some contexts, it is natural to handle more refined structures than pure sparsity, such as for instance group sparsity. Sparse-Group Lasso has recently been introduced in the context of l…
New methods solve tensor-on-tensor regression with unknown rank, revealing benefits of over-parameterization.
problem Connecting tensor responses to tensor covariates with unknown intrinsic rank.
method Riemannian gradient descent and Riemannian Gauss-Newton methods for tensor-on-tensor regression.
result Riemannian optimization methods converge linearly and quadratically to a statistically optimal estimate in rank over-parameterized settings.
The committee machine: Computational to statistical gaps in learning a two-layers neural networkcs.LG
Heuristic tools from statistical physics have been used in the past to locate the phase transitions and compute the optimal learning and generalization errors in the teacher-student scenario in multi-layer neural networks. In this contribution, we provide a rigorous justification of these approaches for a two-layers ne…
Unified framework for adaptive learning systems using consolidation and expansion operations.
problem Managing the balance between consolidating known knowledge and expanding into new evidence in adaptive learning systems.
method Introduces Consolidation-Expansion Operator Mechanics (OpMech) with the order-gap metric to control the balance.
result The order-gap signal provides real-time control and termination guarantees for adaptive learning systems.
Study on detecting and recovering hidden dense cycles in random graphs.
problem Detecting and recovering hidden dense cycles in random graphs.
method Information-theoretic analysis of thresholds for detection and recovery.
result Characterization of information-theoretic thresholds for detection and recovery.
A new algorithm COVA-FC improves subgroup-fair clustering efficiency.
problem Challenges in making cluster assignments independent of sensitive attributes in subgroups.
method Defining a subgroup-fairness gap, deriving a covariance-based surrogate, and introducing a continuous relaxation for efficient optimization.
result COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency.
Efficient method for tensor linear form inference with noisy incomplete data.
problem Statistical inference of tensor linear forms with incomplete and noisy observations.
method Initial estimate + debiasing + one-step power iteration.
result Optimal uncertainty quantification and statistical-to-computational gaps examined.
We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the d…
Using the classification of transitive groups we classify indecomposable quandles of size <36. This classification is available in Rig, a GAP package for computations related to racks and quandles. As an application, the list of all indecomposable quandles of size <36 not of type D is computed.
New framework bridges climate science and ML for easier climate model emulation.
problem High computational costs and mistrust of ML methods in climate models.
method Integrating climate science and machine learning perspectives to design easy-to-adopt emulators.
result Demonstrated reliability of emulators designed to address specific tasks.
We study the fundamental tradeoffs between statistical accuracy and computational tractability in the analysis of high dimensional heterogeneous data. As examples, we study sparse Gaussian mixture model, mixture of sparse linear regressions, and sparse phase retrieval model. For these models, we exploit an oracle-based…