:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Hsieh, Jun-Ting, Kane, Daniel M., Kothari, Pravesh K., Li, Jerry, Mohanty, Sidhanth, Tiegel, Stefan
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Probability
Online Access:	https://arxiv.org/abs/2601.05850
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Explicit Lossless Vertex Expanders
by: Hsieh, Jun-Ting, et al.
Published: (2025)

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

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

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

Explicit two-sided unique-neighbor expanders
by: Hsieh, Jun-Ting, et al.
Published: (2023)

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

Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
by: Huang, Brice, et al.
Published: (2025)

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

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

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

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

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

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)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

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

Eigenvalue Bounds for Random Matrices via Zerofreeness
by: Mohanty, Sidhanth, et al.
Published: (2025)

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

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)

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

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

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

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

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
by: Bangachev, Kiril, et al.
Published: (2024)

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

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

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

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)