We study random 2-dimensional complexes in the Linial - Meshulam model and find torsion in their fundamental groups at various regimes. We find a simple algorithmically testable criterion for a subcomplex of a random 2-complex to be aspherical; this implies that any aspherical subcomplex of a random 2-complex satisfies…
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,657 papers · 148 categories
Trend · papers per month
48 results for “random complexes”
Random complexes can be embedded linearly if certain conditions on parameters are met.
problem Embedding random simplicial complexes linearly in Euclidean space.
method Established strict inequalities on parameters for linear embedding into R^(2d).
result Necessary and sufficient conditions for linear embedding of random complexes.
Random walks on cell complexes link to Laplacians and Novikov-Shubin invariants.
problem Computing Novikov-Shubin invariants for complex cell structures.
method Construct random walks on cell complexes, relate to Laplacians, and use return probabilities.
result Novikov-Shubin invariants can be recovered from random walk return probabilities.
Enhances random forest consistency and introduces DMRF for improved performance.
problem Improving the consistency and efficiency of random forest algorithms.
method Strengthened proof methods and propose DMRF algorithm.
result DMRF achieves better theoretical and experimental performance than previous variants.
Random branched covers of groups are homotopy equivalent to geometrically small cancellation complexes.
problem Understanding the topological properties of random branched covers of groups.
method Constructing a random model for branched covers and showing asymptotic homotopy equivalence to geometrically small cancellation complexes.
result The fundamental group of a random branched cover is Gromov hyperbolic and has small cohomological dimension.
We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton…
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…
Gradient boosting with randomized trees reduces discontinuities and complexity.
problem Discontinuities in regression functions due to sparse training data.
method Gradient boosting machine with partially randomized decision trees.
result Improves robustness and computational efficiency of gradient boosting.
Randomness is crucial for stability in learning and statistics, especially for differential privacy.
problem Quantifying the amount of randomness needed for algorithmic stability.
method Weak-to-strong boosting theorem for stability, characterizing randomness complexity of PAC Learning.
result Randomness complexity is tightly controlled by the best replication probability of any deterministic algorithm solving the task.
Algorithm learns CNF formulas from random solutions under specific conditions.
problem Learning a CNF formula from uniform random solutions.
method Revisits Valiant's algorithm and applies Lovász local lemma conditions.
result Significantly reduces sample complexity for learning CNFs.
We propose reinforcement learning on simple networks consisting of random connections of spiking neurons (both recurrent and feed-forward) that can learn complex tasks with very little trainable parameters. Such sparse and randomly interconnected recurrent spiking networks exhibit highly non-linear dynamics that transf…
Random Heegaard splittingsmath.GT
A random Heegaard splitting is a 3-manifold obtained by using a random walk of length n on the mapping class group as the gluing map between two handlebodies. We show that the joint distribution of random walks of length n and their inverses is asymptotically independent, and converges to the product of the harmonic an…
We consider -dimensional random simplicial complexes that are generated from the binomial random -uniform hypergraph by taking the downward-closure, where . For each , we determine when all cohomology groups with coefficients in from dimension one up to vanish and…
We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erdős-Rényi random graphs. We find the threshold for simple connectivity to be p = n^{-1/2}. This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be p = 2 log(…
Probabilistic model for exhaustion in infinite-genus curve complexes.
problem Action rigidity in infinite-genus curve complexes.
method Costa and Farber's model for random simplicial complexes.
result Probabilistic evidence for exhaustion via rigid expansions.
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecs.LG
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Our main result is that for densities a random group in the square model has the Haagerup property and is residually finite. Moreover, we generalize the Isoperimetric Inequality, to some class of non-planar diagrams and, using this, we introduce a system of modified hypergraphs providing the structure o…
Hierarchical randomized smoothing improves model robustness for complex data.
problem Certifying robustness on complex data (e.g. images, graphs) is challenging.
method Add random noise to a randomly selected subset of entities in a hierarchical manner.
result Hierarchical randomized smoothing yields stronger robustness guarantees with high accuracy.
A non-Hermitean extension of paradigmatic Wishart random matrices is introduced to set up a theoretical framework for statistical analysis of (real, complex and real quaternion) stochastic time series representing two "remote" complex systems. The first paper in a series provides a detailed spectral theory of non-Hermi…
As integrated circuits have become progressively more complex, constrained random stimulus has become ubiquitous as a means of stimulating a designs functionality and ensuring it fully meets expectations. In theory, random stimulus allows all possible combinations to be exercised given enough time, but in practice with…
Develops accelerated methods for optimization using low-dimensional projected-gradient information.
problem Optimization with low-dimensional projected-gradient information and Nesterov acceleration.
method Randomized-subspace Nesterov accelerated gradient methods for smooth convex and strongly convex optimization.
result Established accelerated oracle-complexity guarantees and unified basis for comparing sketch families.
Study compares memorization of SimCLR to supervised and random labels training.
problem Understanding memorization in contrastive learning.
method Investigated SimCLR's memorization properties compared to supervised and random labels training.
result SimCLR's memorization is similar to random labels training in terms of training object complexity distribution.
Survey on random walks on mapping class groups and their properties.
problem Understanding random walks on mapping class groups.
method Analyzing actions on Teichmüller spaces and curve complexes.
result Laws of large numbers and central limit theorems for random walks.
Over the last decade, both the neural network and kernel adaptive filter have successfully been used for nonlinear signal processing. However, they suffer from high computational cost caused by their complex/growing network structures. In this paper, we propose two random Euler filters for complex-valued nonlinear filt…
We establish spectral theorems for random walks on mapping class groups of connected, closed, oriented, hyperbolic surfaces, and on . In both cases, we relate the asymptotics of the stretching factor of the diffeomorphism/automorphism obtained at time of the random walk to the Lyapunov exponent of …
In this paper we study the homology of a random Cech complex generated by a homogeneous Poisson process in a compact Riemannian manifold M. In particular, we focus on the phase transition for "homological connectivity" where the homology of the complex becomes isomorphic to that of M. The results presented in this pape…
We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erdős-Rényi random graphs. We find the threshold for simple connectivity to be p = n^{-1/2}. This is in contrast to the threshold for vanishing of the first homology group, which was shown earlier by Linial and Meshulam to be p = 2 log(…
This paper explores and analyzes two randomized designs for robust Principal Component Analysis (PCA) employing low-dimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by low dimensional embedding, while in the other, sketching is based on random column and row …
We present extremal constructions connected with the property of simplicial collapsibility. (1) For each , there are collapsible (and shellable) simplicial -complexes with only one free face. Also, there are non-evasive -complexes with only two free faces. (Both results are optimal in all dimensions.) (2…
We improve random forest consistency and performance with DMRF, a new variant.
problem Improving the consistency and performance of random forest models.
method Developed DMRF, a data-driven multinomial random forest, by modifying proof methods and improving data utilization.
result DMRF achieves strong consistency with probability 1, surpassing previous models in classification tasks.
Radical Complexityq-fin.GN
Reviews six finance topics, including 'radical complexity'.
problem None explicitly stated, focuses on research directions.
method Informal review and discussion of open questions.
result No specific key result mentioned, focuses on research directions.
We propose a novel probabilistic method for detection of objects in noisy images. The method uses results from percolation and random graph theories. We present an algorithm that allows to detect objects of unknown shapes in the presence of random noise. The algorithm has linear complexity and exponential accuracy and …
We adapt the idea of random projections applied to the output space, so as to enhance tree-based ensemble methods in the context of multi-label classification. We show how learning time complexity can be reduced without affecting computational complexity and accuracy of predictions. We also show that random output spac…
This study examines a single attention layer's capabilities using random features.
problem Understanding the learning and generalization of a single multi-head attention layer.
method Random feature setting with large number of heads, frozen query and key matrices, and trainable value matrices.
result Random-feature attention layer can express a broad class of permutation-invariant target functions.
Improves efficiency of random feature approximations for dot product kernels.
problem Efficiency of random feature approximations for dot product kernels.
method Generalization of existing random feature approximations using complex-valued random features, theoretical analysis of variances, data-driven optimization approach.
result Complex-valued random features can significantly reduce the variances of approximations.
We investigate the random dynamics of rational maps on the Riemann sphere and the dynamics of semigroups of rational maps on the Riemann sphere. We show that regarding random complex dynamics of polynomials, in most cases, the chaos of the averaged system disappears, due to the cooperation of the generators. We investi…
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.
RSHT algorithm simplifies complex shapes to points.
problem Simplifying complex shapes to points in higher dimensions.
method Combines simplicial collapses and expansions.
result Reduces triangulated d-manifolds to points using RSHT.
Paper introduces a new, tractable measure of model complexity.
problem Need for a reliable measure of model complexity.
method Mathematically rigorous measure based on gradient similarities.
result Generalizes to various model types and insights into double descent.
New algorithm trains deep neural networks without global optimization.
problem Training deep neural networks efficiently and without global optimization.
method Uses random complex exponential activation functions and Markov Chain Monte Carlo sampling.
result Consistently attains theoretical approximation rate for residual networks.
Topology helps estimate chromatic numbers of random graphs on spheres.
problem Estimating chromatic numbers of random graphs on spheres.
method Topology, specifically connectivity of Lóvasz's neighborhood complex.
result Connectivity bound is useful in dimensions 1 and 2, but generally poor.
Complex and Quaternionic Analogues of Busemann's Random Simplex and Intersection Inequalitiesmath.MG
The paper extends Busemann's inequalities to complex and quaternionic spaces.
problem Extending Busemann's inequalities to complex and quaternionic vector spaces.
method Proof leverages a monotonicity property under symmetrization with respect to complex or quaternionic hyperplanes.
result Standard Steiner symmetrization does not exhibit the monotonicity property in complex or quaternionic spaces.
Many random processes can be simulated as the output of a deterministic model accepting random inputs. Such a model usually describes a complex mathematical or physical stochastic system and the randomness is introduced in the input variables of the model. When the statistics of the output event are known, these input …
Integrates MRF into multimodal VAE for better complex intermodal interactions.
problem Lack of effective modeling of complex intermodal interactions in multimodal VAEs.
method Incorporates Markov Random Field into prior and posterior distributions of multimodal VAE.
result Demonstrates superior performance in managing complex intermodal dependencies.
Asymptotic Normality of Divisors of Random Holomorphic Sections on Non-compact Complex Manifoldsmath.CV
Study shows normal distribution in divisor counts of random sections on complex manifolds.
problem Distribution of divisors on complex manifolds.
method Central limit theorem for smooth linear statistics of Gaussian sections.
result Asymptotic normality of divisor counts.
New framework improves worst-case generalization bounds for stochastic optimization.
problem Challenges in providing generalization guarantees for stochastic optimization algorithms.
method Introduces random set stability and empirically relevant complexity measures to avoid intractable mutual information terms.
result Bounded worst-case generalization error in terms of random set stability and empirically relevant complexity measures.
Random feature matrices' singular values concentrate near their full expectation in high dimensions.
problem Characterizing the spectra of random feature matrices for regression problems.
method Analyzing two settings of input variables (random or well-separated) with conditions on dimension, complexity ratio, and sampling variance.
result The singular values of random feature matrices concentrate near their full expectation and near one with high probability.
The contact graph of a CAT(0) cubical complex has unbounded structure and a Gaussian CLT for random walks.
problem Understanding the structure and behavior of random walks on CAT(0) cubical complexes.
method Proved the contact graph is unbounded and homeomorphic to the boundary. Reformulated Caprace-Sageev's theorem. Proved a Central Limit Theorem for random walks.
result A Central Limit Theorem for random walks on CAT(0) cubical complexes, with a non-degenerate Gaussian distribution.