Imagen de Portada

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Lela, Marko
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Information Theory 68Q17, 68Q15, 03F20 F.1.3; F.2.2; G.2.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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)

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

Shifted Partial Derivative Polynomial Rank and Codimension
por: Edwards, Darren J.
Publicado: (2025)

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

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

NP-hard problems are not in BQP
por: Czerwinski, Reiner
Publicado: (2023)

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

Complexities of Well-Quasi-Ordered Substructural Logics
por: Galatos, Nikolaos, et al.
Publicado: (2025)

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

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

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
por: Bannach, Max, et al.
Publicado: (2025)

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

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

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

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
por: Kumar, Mrinal, et al.
Publicado: (2018)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
por: Grochow, Joshua A., et al.
Publicado: (2025)

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

Separation of PSPACE and EXP
por: Czerwinski, Reiner
Publicado: (2021)

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

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

Dichotomy for orderings?
por: Kun, Gábor, et al.
Publicado: (2025)

Generalisations of Matrix Partitions : Complexity and Obstructions
por: Barsukov, Alexey, et al.
Publicado: (2021)

A correspondence between the time and space complexity
por: Latkin, Ivan V.
Publicado: (2023)

The Optimizer Quotient and the Certification Trilemma
por: Simas, Tristan
Publicado: (2026)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
por: Emmerich, Michael T. M., et al.
Publicado: (2026)

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

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

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)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
por: Grochow, Joshua A., et al.
Publicado: (2022)

I/O complexity and pebble games with partial computations
por: Sobczyk, Aleksandros
Publicado: (2024)

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

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

Approximate Keys and Functional Dependencies in Incomplete Databases With Limited Domains-Algorithmic Perspective
por: Al-atar, Munqath, et al.
Publicado: (2024)

Approximate Integrity Constraints in Incomplete Databases With Limited Domains
por: Al-atar, Munqath, et al.
Publicado: (2024)

Quantum algorithms through graph composition
por: Cornelissen, Arjan
Publicado: (2025)

Quantum walks through generalized graph composition
por: Cornelissen, Arjan
Publicado: (2025)

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

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

Which graph motif parameters count?
por: Bläser, Markus, et al.
Publicado: (2025)