:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Lutz, Neil, Martin, Spencer Park, White, Rain
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Probability
Online Access:	https://arxiv.org/abs/2507.05475
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

Pseudorandom Permutations from Random Reversible Circuits
by: He, William, et al.
Published: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Random Systems of Holomorphic Sections of a Sequence of Line bundles on Compact Kähler Manifolds
by: Bojnik, Afrim, et al.
Published: (2024)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

Equidistribution of Zeros of Random Polynomials and Random Polynomial mappings on $\mathbb{C}^m$
by: Günyüz, Ozan
Published: (2022)

The Probability Spaces of QuickSort
by: Nadareishvili, George, et al.
Published: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
by: Williamson, Christopher
Published: (2026)

Perfect sampling from rapidly mixing Markov chains
by: Göbel, Andreas, et al.
Published: (2024)

Rigorous Implications of the Low-Degree Heuristic
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Inconsistency Probability of Sparse Equations over F2
by: Horak, P., et al.
Published: (2026)

Algorithmic Randomness and Probabilistic Laws
by: Barrett, Jeffrey A., et al.
Published: (2023)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Permanents of random matrices over finite fields
by: Hunter, Zach, et al.
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

Equidistribution for Random Polynomials and Systems of Random Holomorphic Sections
by: Günyüz, Ozan
Published: (2024)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
by: Kızıldağ, Eren C.
Published: (2023)

Separating complexity classes of LCL problems on grids
by: Berlow, Katalin, et al.
Published: (2025)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
by: Li, Cheuk Ting
Published: (2024)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
by: Gamarnik, David, et al.
Published: (2023)

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
by: Bandeira, Afonso S., et al.
Published: (2024)

Asymptotic Mass Distribution of Random Holomorphic Sections
by: Bayraktar, Turgay, et al.
Published: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
by: Dhawan, Abhishek, et al.
Published: (2024)

The Expected Depth of Random Real Algebraic Plane Curves
by: Bayraktar, Turgay, et al.
Published: (2021)

Random interpolation in the Nevanlinna and Smirnov classes and related spaces
by: Lamberti, Giuseppe
Published: (2024)

Random Carleson Sequences for the Hardy space on the Polydisc and the Unit Ball
by: Chalmoukis, Nikolaos, et al.
Published: (2024)

Asymptotic Normality of Divisors of Random Holomorphic Sections on Non-compact Complex Manifolds
by: Bojnik, Afrim, et al.
Published: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
by: Li, Tiange, et al.
Published: (2026)

The Critical Beta-splitting Random Tree IV: Mellin analysis of Leaf Height
by: Aldous, David, et al.
Published: (2024)

Algorithmically Optimal Outer Measures
by: Lutz, Jack H., et al.
Published: (2020)

Symmetric Perceptrons, Number Partitioning and Lattices
by: Vafa, Neekon, et al.
Published: (2025)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
by: Gamarnik, David
Published: (2025)