:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Horak, P., Semaev, I.
Format:	Preprint
Published:	2026
Subjects:	Probability Computational Complexity
Online Access:	https://arxiv.org/abs/2603.24890
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

Lines in Every Direction with No ee-Random Points
by: Lutz, Neil, et al.
Published: (2025)

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

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, 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)

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)

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

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

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

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

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

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

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

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)

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

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

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

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

Average-Case Reductions for $k$-XOR and Tensor PCA
by: Bresler, Guy, et al.
Published: (2026)

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)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

Characterization of the set of zero-noise limits measures of perturbed cellular automata
by: Marsan, Hugo, et al.
Published: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

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

Hole Phenomenon of Gaussian Analytic Functions with Power-exponential Weights
by: Du, Yun-Heng
Published: (2026)

Circle packing and Riemann uniformization of random planar maps in an ergodic scale-free environment
by: Holden, Nina, et al.
Published: (2026)

A survey on asymptotic equilibrium distribution of zeros of random holomorphic sections
by: Marinescu, George, et al.
Published: (2025)

A method of solution for the inverse problem for $h$-functions of planar Brownian motion
by: Markowsky, Greg, et al.
Published: (2024)

Zero distribution of power series and binary correlation of coefficients
by: Benatar, Jacques, et al.
Published: (2021)

A note on Loewner energy, conformal restriction and Werner's measure on self-avoiding loops
by: Wang, Yilin
Published: (2018)

On a problem of E. Meckes for the unitary eigenvalue process on an arc
by: Kryvonos, Liudmyla, et al.
Published: (2024)