Cover Image

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gamarnik, David, Mossel, Elchanan, Zadik, Ilias
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Probability Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

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

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
by: Chen, Siyu, et al.
Published: (2025)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
by: Yu, Xifan, et al.
Published: (2024)

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

A Bayesian Proof and Interpretation of Talagrand's Majorizing Measure Theorem
by: Zadik, Ilias
Published: (2026)

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
by: Tsirkas, Konstantinos, et al.
Published: (2026)

On the Hardness of Learning One Hidden Layer Neural Networks
by: Li, Shuchen, et al.
Published: (2024)

Detecting Mutual Excitations in Non-Stationary Hawkes Processes
by: Mossel, Elchanan, et al.
Published: (2026)

Gaussian Broadcast on Grids
by: Jiradilok, Pakawut, et al.
Published: (2024)

Detecting Abrupt Changes in Point Processes: Fundamental Limits and Applications
by: Brandenberger, Anna, et al.
Published: (2025)

The stochastic block model has the overlap graph property for modularity
by: Bhamidi, Shankar, et al.
Published: (2026)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
by: Sohn, Youngtak, et al.
Published: (2025)

Finding Super-spreaders in Network Cascades
by: Mossel, Elchanan, et al.
Published: (2024)

Almost‐Linear Planted Cliques Elude the Metropolis Process
by: Zongchen Chen, et al.
Published: (2025)

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

The Fundamental Limits of Recovering Planted Subgraphs
by: Lee, Daniel, et al.
Published: (2025)

On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem
by: Lovig, Maxwell, et al.
Published: (2024)

Inference of rankings planted in random tournaments
by: Kunisky, Dmitriy, et al.
Published: (2024)

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
by: Mossel, Elchanan, et al.
Published: (2024)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
by: Tang, Runshi, et al.
Published: (2026)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

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

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

Stochastic block models with many communities and the Kesten--Stigum bound
by: Chin, Byron, et al.
Published: (2025)

Detection of local geometry in random graphs: information-theoretic and computational limits
by: Bok, Jinho, et al.
Published: (2026)

A Generalisation of Ville's Inequality to Monotonic Lower Bounds and Thresholds
by: Koolen, Wouter M., et al.
Published: (2025)

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

Testing Convex Truncation
by: De, Anindya, et al.
Published: (2023)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
by: Fu, Daniel, et al.
Published: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
by: R., Abhishek Hegade K., et al.
Published: (2025)

Strong Low Degree Hardness for the Number Partitioning Problem
by: Mallarapu, Rushil, et al.
Published: (2025)

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
by: Bhamidi, Shankar, et al.
Published: (2025)

Statistical inference of a ranked community in a directed graph
by: Kunisky, Dmitriy, et al.
Published: (2024)

Sharp Threshold for the Convergence of Nonstationary Averaging
by: Lepsveridze, Saba, et al.
Published: (2026)

Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
by: Mossel, Elchanan, et al.
Published: (2022)

Tensor cumulants for statistical inference on invariant distributions
by: Kunisky, Dmitriy, et al.
Published: (2024)

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

Sharp bounds for products of dependent random variables
by: Blier-Wong, Christopher, et al.
Published: (2026)

Random Circuit Sampling: Fourier Expansion and Statistics
by: Kalai, Gil, et al.
Published: (2024)