:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autor principal:	Levin, Leonid A.
Formato:	Preprint
Publicado:	2022
Materias:	Computational Complexity 68Q17 F.2.2
Acceso en línea:	https://arxiv.org/abs/2209.09121
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On Small-depth Frege Proofs for PHP
por: Håstad, Johan
Publicado: (2024)

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

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

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

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

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

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

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

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

Quoridor is PSPACE-Complete
por: Drop, Marius, et al.
Publicado: (2026)

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

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

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

Computational Complexity of Determining the Assembly Index
por: Masierak, Piotr
Publicado: (2026)

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

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

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

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

Treewidth Inapproximability and Tight ETH Lower Bound
por: Bonnet, Édouard
Publicado: (2024)

Completeness classes in algebraic complexity theory
por: Bürgisser, Peter
Publicado: (2024)

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

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

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

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

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

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

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

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

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

An SoS Entropy Dichotomy via Windowed Hypercontractivity
por: Lela, Marko
Publicado: (2025)

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

Count-Free Weisfeiler--Leman and Group Isomorphism
por: Collins, Nathaniel A., et al.
Publicado: (2022)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
por: Grochow, Joshua A., et al.
Publicado: (2021)

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

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

How to compute the volume in low dimension?
por: Cornelissen, Arjan, et al.
Publicado: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
por: Philip, Geevarghese, et al.
Publicado: (2026)

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

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

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