:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Lutz, Neil, Martin, Spencer Park, White, Rain
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Probability
Online-Zugang:	https://arxiv.org/abs/2507.05475
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
von: Tulsiani, Madhur, et al.
Veröffentlicht: (2024)

Communication with Imperfectly Shared Randomness
von: Canonne, Clément L., et al.
Veröffentlicht: (2014)

Pseudorandom Permutations from Random Reversible Circuits
von: He, William, et al.
Veröffentlicht: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

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

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

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

The Probability Spaces of QuickSort
von: Nadareishvili, George, et al.
Veröffentlicht: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
von: Williamson, Christopher
Veröffentlicht: (2026)

Perfect sampling from rapidly mixing Markov chains
von: Göbel, Andreas, et al.
Veröffentlicht: (2024)

Rigorous Implications of the Low-Degree Heuristic
von: Hsieh, Jun-Ting, et al.
Veröffentlicht: (2026)

Inconsistency Probability of Sparse Equations over F2
von: Horak, P., et al.
Veröffentlicht: (2026)

Algorithmic Randomness and Probabilistic Laws
von: Barrett, Jeffrey A., et al.
Veröffentlicht: (2023)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
von: Kush, Deepanshu
Veröffentlicht: (2026)

On hardness of computing analytic Brouwer degree
von: Chakraborty, Somnath
Veröffentlicht: (2023)

Permanents of random matrices over finite fields
von: Hunter, Zach, et al.
Veröffentlicht: (2026)

Optimal Union Probability Interval Is NP-Hard
von: Kaski, Petteri, et al.
Veröffentlicht: (2026)

Equidistribution for Random Polynomials and Systems of Random Holomorphic Sections
von: Günyüz, Ozan
Veröffentlicht: (2024)

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

Separating complexity classes of LCL problems on grids
von: Berlow, Katalin, et al.
Veröffentlicht: (2025)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
von: Li, Cheuk Ting
Veröffentlicht: (2024)

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

Critical window for approximate counting in dense Ising models
von: Galanis, Andreas, et al.
Veröffentlicht: (2026)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
von: Bandeira, Afonso S., et al.
Veröffentlicht: (2024)

Asymptotic Mass Distribution of Random Holomorphic Sections
von: Bayraktar, Turgay, et al.
Veröffentlicht: (2025)

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

The Expected Depth of Random Real Algebraic Plane Curves
von: Bayraktar, Turgay, et al.
Veröffentlicht: (2021)

Random interpolation in the Nevanlinna and Smirnov classes and related spaces
von: Lamberti, Giuseppe
Veröffentlicht: (2024)

Random Carleson Sequences for the Hardy space on the Polydisc and the Unit Ball
von: Chalmoukis, Nikolaos, et al.
Veröffentlicht: (2024)

Asymptotic Normality of Divisors of Random Holomorphic Sections on Non-compact Complex Manifolds
von: Bojnik, Afrim, et al.
Veröffentlicht: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
von: Li, Rupert, et al.
Veröffentlicht: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
von: Huang, Neng, et al.
Veröffentlicht: (2024)

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

The Critical Beta-splitting Random Tree IV: Mellin analysis of Leaf Height
von: Aldous, David, et al.
Veröffentlicht: (2024)

Algorithmically Optimal Outer Measures
von: Lutz, Jack H., et al.
Veröffentlicht: (2020)

Symmetric Perceptrons, Number Partitioning and Lattices
von: Vafa, Neekon, et al.
Veröffentlicht: (2025)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
von: Gamarnik, David
Veröffentlicht: (2025)