Copertina

Smaller Depth-2 Linear Circuits for Disjointness Matrices

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Ye, Lixi
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity 68Q17, 68Q25 F.2.0; F.1.1
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
di: Alpay, Faruk, et al.
Pubblicazione: (2026)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
di: Filmus, Yuval, et al.
Pubblicazione: (2020)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
di: Susukita, Kosuke, et al.
Pubblicazione: (2026)

The Serial Scaling Hypothesis
di: Liu, Yuxi, et al.
Pubblicazione: (2025)

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)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
di: Bodnar, Levente
Pubblicazione: (2024)

Extended Nullstellensatz proof systems
di: Krajicek, Jan
Pubblicazione: (2023)

The Complexity of Iterated Reversible Computation
di: Eppstein, David
Pubblicazione: (2021)

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

The Complexity of Resilience Problems via Valued Constraint Satisfaction
di: Bodirsky, Manuel, et al.
Pubblicazione: (2023)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
di: Huseynzade, Rafig
Pubblicazione: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
di: Asimi, Kristina, et al.
Pubblicazione: (2020)

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

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

On the existence of strong proof complexity generators
di: Krajicek, Jan
Pubblicazione: (2022)

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

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

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

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)

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

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
di: Shalunov, Yakov
Pubblicazione: (2023)

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

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

Linear average-case complexity of algorithmic problems in groups
di: Olshanskii, Alexander, et al.
Pubblicazione: (2022)

Greedy Poisson Rejection Sampling
di: Flamich, Gergely
Pubblicazione: (2023)