:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chen, Lijie, Jin, Ce, Santhanam, Rahul, Williams, Ryan
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2203.14379
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Polynomial-Time Pseudodeterministic Construction of Primes
von: Chen, Lijie, et al.
Veröffentlicht: (2023)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
von: Lu, Jiaqi, et al.
Veröffentlicht: (2025)

From Proof Complexity to Circuit Complexity via Interactive Protocols
von: Arteche, Noel, et al.
Veröffentlicht: (2024)

Constructive Separations from Gate Elimination
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

Simulating Time With Square-Root Space
von: Williams, R. Ryan
Veröffentlicht: (2025)

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

A Theory for Probabilistic Polynomial-Time Reasoning
von: Chen, Lijie, et al.
Veröffentlicht: (2026)

Effective Guessing Has Unlikely Consequences
von: Salamon, András Z., et al.
Veröffentlicht: (2021)

Diffusion Language Models are Provably Optimal Parallel Samplers
von: Jiang, Haozhe, et al.
Veröffentlicht: (2025)

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

Certificate Games and Consequences for the Classical Adversary Bound
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2022)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Separations in Proof Complexity and TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2022)

Super Unique Tarski is in UEOPL
von: Fearnley, John, et al.
Veröffentlicht: (2024)

Separations between Combinatorial Measures for Transitive Functions
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2021)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
von: Bhattacharjee, Sutanay, et al.
Veröffentlicht: (2026)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
von: Samar, Sahil, et al.
Veröffentlicht: (2026)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
von: Çivril, Ali
Veröffentlicht: (2021)

Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)
von: Ducros, Vivien, et al.
Veröffentlicht: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2024)

Theoretical limitations of multi-layer Transformer
von: Chen, Lijie, et al.
Veröffentlicht: (2024)

An Improved Construction of Variety-Evasive Subspace Families
von: Andrews, Robert, et al.
Veröffentlicht: (2026)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

Lossy Catalytic Computation
von: Gupta, Chetan, et al.
Veröffentlicht: (2024)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

New Techniques for Constructing Rare-Case Hard Functions
von: Nareddy, Tejas, et al.
Veröffentlicht: (2024)

Parallel Play Saves Quantifiers
von: Carmosino, Marco, et al.
Veröffentlicht: (2024)

Quantum information advantage based on Bell inequalities
von: Jain, Rahul, et al.
Veröffentlicht: (2026)

Computational complexity of isometric tensor network states
von: Malz, Daniel, et al.
Veröffentlicht: (2024)

Monotone Contractions
von: Batziou, Eleni, et al.
Veröffentlicht: (2024)

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
von: Bshouty, Nader H.
Veröffentlicht: (2025)

Separating Quantum and Classical Advice with Good Codes
von: Bostanci, John, et al.
Veröffentlicht: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
von: Agarwal, Avantika, et al.
Veröffentlicht: (2024)

Separations in query complexity for total search problems
von: Ben-David, Shalev, et al.
Veröffentlicht: (2024)

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

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
von: Çivril, Ali
Veröffentlicht: (2021)

Improved Circuit Lower Bounds and Quantum-Classical Separations
von: Grewal, Sabee, et al.
Veröffentlicht: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2024)