Cover Image

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Meir, Or
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity 68Q17
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Lower Bounds by Sample-to-Query Lifting
by: Wang, Qisheng, et al.
Published: (2023)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

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

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

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

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

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

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

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

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

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

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

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

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

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

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

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

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

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

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Recent Advances in Debordering Methods
by: Dutta, Pranjal, et al.
Published: (2025)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

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

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
by: Chattopadhyay, Eshan, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

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