Copertina

On Small-depth Frege Proofs for PHP

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Håstad, Johan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity 68Q17 F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
di: Eua-anant, Pakapim, et al.
Pubblicazione: (2025)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
di: Levin, Leonid A.
Pubblicazione: (2022)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
di: Kelley, Zander, et al.
Pubblicazione: (2023)

DAG Scheduling in the BSP Model
di: Papp, Pál András, et al.
Pubblicazione: (2023)

NP-hardness of p-adic linear regression
di: Baker, Gregory D.
Pubblicazione: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
di: Böhnlein, Toni, et al.
Pubblicazione: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
di: Lela, Marko
Pubblicazione: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
di: Dorochko, Leonid, et al.
Pubblicazione: (2026)

Quoridor is PSPACE-Complete
di: Drop, Marius, et al.
Pubblicazione: (2026)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
di: Liao, Chao, et al.
Pubblicazione: (2022)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
di: Lobe, Elisabeth, et al.
Pubblicazione: (2021)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
di: Saffidine, Abdallah, et al.
Pubblicazione: (2025)

The Word Problem for Products of Symmetric Groups
di: Simon, Hans U.
Pubblicazione: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
di: Xia, Mingji
Pubblicazione: (2026)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
di: Phillips, Reed
Pubblicazione: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
di: Lagerkvist, Victor, et al.
Pubblicazione: (2026)

Computational Complexity of Determining the Assembly Index
di: Masierak, Piotr
Pubblicazione: (2026)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
di: Lela, Marko
Pubblicazione: (2025)

Completeness classes in algebraic complexity theory
di: Bürgisser, Peter
Pubblicazione: (2024)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
di: Chen, Yijia, et al.
Pubblicazione: (2023)

On bounded depth proofs for Tseitin formulas on the grid; revisited
di: Håstad, Johan, et al.
Pubblicazione: (2022)

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Folding One Polyhedral Metric Graph into Another
di: Chung, Lily, et al.
Pubblicazione: (2024)

Hive is PSPACE-Hard
di: Andel, Daniël, et al.
Pubblicazione: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
di: Ye, Lixi
Pubblicazione: (2026)

Two-player Domino games
di: de Menibus, Benjamin Hellouin, et al.
Pubblicazione: (2023)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
di: von Liechtenstein, Maximilian R. P.
Pubblicazione: (2025)

Graph polynomials: some questions on the edge
di: Farr, Graham, et al.
Pubblicazione: (2024)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
di: Lela, Marko
Pubblicazione: (2025)

Quantum Time-Space Tradeoffs for Matrix Problems
di: Beame, Paul, et al.
Pubblicazione: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

Induced Disjoint Paths Without an Induced Minor
di: Aboulker, Pierre, et al.
Pubblicazione: (2025)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
di: Kapron, Bruce M., et al.
Pubblicazione: (2024)

The Impact of Partial Computations on the Red-Blue Pebble Game
di: Papp, Pál András, et al.
Pubblicazione: (2025)

Optimal Portfolio Compression for Priority-Proportional Clearing with Defaulting Costs
di: Csáji, Gergely, et al.
Pubblicazione: (2026)

The Optimizer Quotient and the Certification Trilemma
di: Simas, Tristan
Pubblicazione: (2026)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
di: Rossman, Benjamin
Pubblicazione: (2024)