We determine the expected curvature polynomial of random real projective varieties given as the zero set of independent random polynomials with Gaussian distribution, whose distribution is invariant under the action of the orthogonal group. In particular, the expected Euler characteristic of such random real projective…
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 “random polynomials”
Random covers of hyperbolic surfaces have a spectral gap with polynomial rate.
problem Finding spectral gaps in random covers of hyperbolic surfaces.
method Applying recent work on spectral gaps to uniformly random covers of closed hyperbolic surfaces.
result Uniformly random degree-n covers of a closed hyperbolic surface have no new Laplacian eigenvalues below a specific threshold with high probability.
Polynomial invariant of quandles counts random link colorings.
problem Counting -colorings of random braids in quandles.
method Average number of -colorings for large .
result The average number of -colorings coincides with a polynomial .
Hermite polynomials improve private data generation by reducing feature count.
problem Infinite-dimensional features in kernel mean embedding are impractical for private data generation.
method Replace random features with Hermite polynomial features, leveraging their ordered nature.
result Hermite polynomial features yield a more accurate approximation of kernel mean embedding with fewer features.
The paper equidistributes zeros of random polynomials and sections on manifolds.
problem Equidistribution of zeros of random polynomials and sections on manifolds.
method Weighted pluripotential theory, asymptotic Bernstein-Markov measures, variance estimation.
result Equidistribution holds for non-i.i.d. random coefficients and non-homogeneous manifolds.
A model of random walk on knot diagrams is used to study the Alexander polynomial and the colored Jones polynomial of knots. In this context, the inverse of the Alexander polynomial of a knot plays the role of an Ihara-Selberg zeta function of a directed weighted graph, counting with weights cycles of random walk on a …
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.
Random surfaces have a strong spectral gap with polynomial rate.
problem Understanding spectral gaps in random hyperbolic surfaces.
method Adapting polynomial method for random matrices to Laplacian on surfaces.
result Laplacian spectral gap at least 1/4 - O(1/g^c) for large g.
Eigenvalues of random hyperbolic surface covers converge to hyperbolic plane's.
problem Eigenvalue rigidity of random hyperbolic surface covers.
method Selberg trace formula and polynomial method.
result Distribution of eigenvalues converges to hyperbolic plane's spectral measure.
The paper studies random dynamical systems of polynomial automorphisms on C^2 and finds mean stability.
problem Random dynamical systems of polynomial automorphisms on C^2.
method Generic random dynamical systems of polynomial automorphisms are shown to have mean stability.
result A generic random dynamical system of polynomial automorphisms on C^2 has mean stability.
Polynomial-time algorithm solves random parity games with high probability.
problem Solving random parity games efficiently.
method SWCP algorithm based on cycles in subgraphs.
result Polynomial-time solution for large-degree games with high probability.
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.
MAP perturbation models have emerged as a powerful framework for inference in structured prediction. Such models provide a way to efficiently sample from the Gibbs distribution and facilitate predictions that are robust to random noise. In this paper, we propose a provably polynomial time randomized algorithm for learn…
We investigate i.i.d. random complex dynamical systems generated by probability measures on finite unions of the loci of holomorphic families of rational maps on the Riemann sphere. We show that under certain conditions on the families, for a generic system, (especially, for a generic random polynomial dynamical system…
Survey on strong convergence in random matrices and its applications.
problem Understanding convergence of random matrices to operators.
method Analysis of operator norms of noncommutative polynomials.
result New insights and applications in random graphs, geometry, and operator algebras.
Study on complexity of random polynomials with deterministic spikes, identifying phase transitions.
problem Complexity of random Gaussian polynomials with deterministic spikes on a sphere.
method Variational formulas, Kac-Rice formula, determinant asymptotics of finite-rank perturbation of Gaussian Wigner matrices.
result Identification of a topological phase transition in the complexity function.
The paper examines linking numbers in grid models and finds polynomial moments.
problem Analyzing linking numbers in grid models.
method Examined linking numbers as a random variable on isotopy classes of 2-component links, computed moments and limits.
result The th moment of the linking number is a polynomial in the grid size with degree , and all odd moments vanish.
Recent years have demonstrated that using random feature maps can significantly decrease the training and testing times of kernel-based algorithms without significantly lowering their accuracy. Regrettably, because random features are target-agnostic, typically thousands of such features are necessary to achieve accept…
The study of random positive 3-strand braids reveals patterns in the roots of their Alexander polynomials.
problem Investigating the roots of Alexander polynomials of random positive 3-strand braids.
method Experimental data analysis, conjectures refinement, and proof of results using tools like the signature function of links and Lyapunov exponent of the Burau representation.
result Generically, at least 69% of the roots of Alexander polynomials are on the unit circle, with a large root-free region near the origin.
Study reveals an equivalence principle for the spectrum of random inner-product kernel matrices in polynomial scaling.
problem Understanding the spectrum of random kernel matrices in polynomial scaling regimes.
method Investigates random matrices with nonlinear kernel functions applied to inner products of uniformly distributed vectors.
result The spectrum of the random kernel matrix is asymptotically equivalent to a simpler matrix model through free additive convolution.
We give upper bounds on the numbers of various classes of polynomials reducible over the integers and over integers modulo a prime and on the number of matrices in SL(n), GL(n) and Sp(2n) with reducible characteristic polynomials, and on polynomials with non-generic Galois groups. We use our result to show that a rando…
Uniformly random permutations converge to regular representation on surface groups.
problem Understanding the behavior of random homomorphisms to symmetric groups.
method Polynomial approximation and random walk analysis.
result Strong convergence of random representations to regular representation.
Random Transformers behave like polynomial models in ICL with asymptotic growth.
problem Understanding in-context learning capabilities of pretrained Transformers.
method Asymptotic analysis of a random Transformer with a fixed first layer and a trained second layer, considering growth in context length, input dimension, hidden dimension, and training parameters.
result The random Transformer's ICL error is equivalent to a finite-degree Hermite polynomial model.
New local-search methods close the gap in sparse tensor PCA.
problem Sparse tensor PCA underperforms compared to other methods.
method Proposes new local-search methods including greedy and random-threshold variants.
result Proves local-search methods close the gap to best known polynomial-time procedures.
In this paper we study the adaptive learnability of decision trees of depth at most 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^…
This paper shows universality in spectrum behavior for random inner-product kernel matrices in polynomial regime.
problem Understanding spectrum behavior of random inner-product kernel matrices in polynomial regime.
method Analyzing matrices formed by a nonlinear function applied entrywise to a sample-covariance matrix, considering i.i.d. entries with all finite moments.
result The spectrum of random inner-product kernel matrices is universally described by the free convolution of the semicircular and Marčenko-Pastur distributions, with relative weights given by expanding the nonlinear function in the Hermite basis.
The aim of this short note is to draw attention to a method by which the partition function and marginal probabilities for a certain class of random fields on complete graphs can be computed in polynomial time. This class includes Ising models with homogeneous pairwise potentials but arbitrary (inhomogeneous) unary pot…
Optimal transport is #P-hard when components are independent, even with approximate solutions.
problem Computational complexity of optimal transport with independent marginals.
method Proved #P-hardness and developed a pseudo-polynomial time approximation algorithm.
result Optimal transport is #P-hard even with independent components and approximate solutions.
We investigate the random dynamics of polynomial maps on the Riemann sphere and the dynamics of semigroups of polynomial maps on the Riemann sphere. In particular, the dynamics of a semigroup of polynomials whose planar postcritical set is bounded and the associated random dynamics are studied. In general, the Juli…
The study shows subgroup separability conditions for specific groups.
problem Conditions for subgroup separability in free-by-cyclic and deficiency 1 groups.
method Analyzes polynomially growing monodromy and asymptotic probability of random groups.
result Random deficiency 1 groups are not subgroup separable with positive probability.
The paper connects Riemannian Gaussian distributions to random matrix theory and diffusion kernels.
problem Analyzing Riemannian Gaussian distributions on symmetric spaces.
method Analytical computation of marginals using orthogonal and skew orthogonal polynomials, and diffusion kernels.
result Riemannian Gaussian distributions are random matrix types, and their probability density functions can be computed analytically.
Polynomial-time algorithm estimates edge density of random graphs with privacy and robustness.
problem Estimating edge density of random graphs while maintaining privacy and robustness.
method Sum-of-squares algorithm for robust edge density estimation and reduction from privacy to robustness.
result Optimal error rate up to logarithmic factors, matching theoretical lower bounds.
New study shows low-degree polynomial algorithms struggle at clause densities close to Fix's.
problem Finding satisfying assignments in random k-SAT formulas at high clause densities.
method Analysis of low-degree polynomial algorithms and a new many-way overlap gap property.
result No efficient algorithms can find satisfying assignments at clause densities close to Fix's.
Study on quantitative aspects of trace polynomials in free groups.
problem Understanding the exact formula and bounds for trace polynomials in free groups.
method Proved exact formula for leading homogeneous part, obtained sharp bounds, studied random words, and provided deterministic algorithm.
result Sharp bounds on the degree of trace polynomials and growth rates of polynomial sizes.
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.
The study reveals the efficiency of sampling from tilted distributions.
problem Sampling from a tilted distribution of an unknown underlying distribution.
method Self-normalized importance sampling to characterize accuracy.
result Polynomial vs super-polynomial sample complexity for bounded vs unbounded distributions.
Knot probabilities in equilateral random polygonscond-mat.stat-mech
Study reveals a universal formula for knotting in random equilateral polygons.
problem Probability of knotting in equilateral random polygons.
method Extensive Monte Carlo simulations with improved algorithms and knot invariants.
result A universal scaling formula for knotting probability with number of edges, involving exponential and power law factors.
A new method reduces the complexity of tensor products from cubic to quadratic, improving both speed and accuracy.
problem Efficiently computing high-dimensional tensor products for polynomial kernels.
method Complex-to-Real (CtR) modification of sketches using complex random projections.
result Achieves state-of-the-art performance in accuracy and speed.
Compact Random Feature Mapsstat.ML
Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this chal…
New algorithms find half-optimal independent sets in sparse graphs.
problem Finding large independent sets in sparse random graphs.
method Low-degree polynomial algorithms.
result Low-degree polynomial algorithms can find independent sets of half-optimal size.
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.
The paper proves an inequality for symmetric polynomials under a fixed point measure.
problem An inequality for elementary symmetric polynomials under a fixed point measure of permutations.
method Constructing differential operators to set up a monotone flow.
result The inequality is proven and is sharp.
Analogous zeta function for twisted Alexander invariants defined.
problem Defining a zeta function for twisted Alexander invariants.
method Modeling random walks on knot diagrams and interpreting Alexander polynomials and Jones polynomials as zeta functions.
result Analogous zeta function expression for twisted Alexander invariants.
The challenges for non-intrusive methods for Polynomial Chaos modeling lie in the computational efficiency and accuracy under a limited number of model simulations. These challenges can be addressed by enforcing sparsity in the series representation through retaining only the most important basis terms. In this work, w…
We study the Gibbs sampling algorithm for continuous determinantal point processes. We show that, given a warm start, the Gibbs sampler generates a random sample from a continuous -DPP defined on a -dimensional domain by only taking number of steps. As an application, we design an algorithm to ge…
Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphismsmath.NT
We prove sharp limit theorems on random walks on graphs with values in finite groups. We then apply these results (together with some elementary algebraic geometry, number theory, and representation theory) to finite quotients of lattices in semisimple Lie groups (specifically SL(n,Z) and Sp(2n, Z) to show that a ``ran…
Paper develops polynomial approximations for complex probability densities.
problem Approximating high-dimensional concentrated probability densities.
method Tensor-product spectral polynomials and KR rearrangements.
result Efficient approximation of complex densities using composite maps.
Polynomial chaos surrogates handle intrinsic noise in stochastic models.
problem Handling intrinsic noise in stochastic models with parametric uncertainty.
method Developed a PCE surrogate on a joint space of intrinsic and parametric uncertainty using Rosenblatt transformations and Karhunen-Loeve expansion.
result Quantified intrinsic noise contribution to model output variance using PCE Sobol indices.