Total Search Problems in $\mathsf{ZPP}$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fleming, Noah, Grosser, Stefan, Jain, Siddhartha, Li, Jiawei, Ren, Hanlin, Shirley, Morgan, Yuan, Weiqiang
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
by: Li, Jiawei, et al.
Published: (2024)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
by: Riazanov, Artur, et al.
Published: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Limits of structures and Total NP Search Problems
by: Ježil, Ondřej
Published: (2023)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
by: Grier, Daniel, et al.
Published: (2026)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
by: Zschetzsche, Lilith, et al.
Published: (2026)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
by: Göller, Stefan, et al.
Published: (2023)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
by: Chen, Lijie, et al.
Published: (2024)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
by: Cao, Yang, et al.
Published: (2024)

Towards a universal gateset for $\mathsf{QMA}_1$
by: Rudolph, Dorian
Published: (2024)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
by: Ren, Hanlin, et al.
Published: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
by: Liu, Yuxi
Published: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Efficient Quantum Hermite Transform
by: Jain, Siddhartha, et al.
Published: (2025)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

Consumable Data via Quantum Communication
by: Gilboa, Dar, et al.
Published: (2024)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
by: Li, Xiaoyu, et al.
Published: (2024)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
by: Kayibi, Koko-Kalambay Kalafan
Published: (2018)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

Information Redistribution Under Reductions in NP Search
by: Wei, Jing-Yuan
Published: (2026)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Complexity Theory meets Ordinary Differential Equations
by: Fono, Adalbert, et al.
Published: (2026)