Cover Image

Negations are powerful even in small depth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cavalar, Bruno, Fabris, Théo Borém, Mukhopadhyay, Partha, Srinivasan, Srikanth, Yehudayoff, Amir
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
by: Mukhopadhyay, Partha, et al.
Published: (2025)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

A Meta-Complexity Characterization of Quantum Cryptography
by: Cavalar, Bruno P., et al.
Published: (2024)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
by: Arvind, V., et al.
Published: (2023)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Trading Determinism for Noncommutativity in Edmonds' Problem
by: Arvind, V., et al.
Published: (2024)

On the Computational Hardness of Quantum One-Wayness
by: Cavalar, Bruno, et al.
Published: (2023)

Ideals, Macaulay Bases, and PCPs
by: Amireddy, Prashanth, et al.
Published: (2025)

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States
by: Cavalar, Bruno, et al.
Published: (2025)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
by: Ron-Zewi, Noga, et al.
Published: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

Learning depth-3 circuits via quantum agnostic boosting
by: Arunachalam, Srinivasan, et al.
Published: (2025)

Two-State Spin Systems with Negative Interactions
by: Fei, Yumou, et al.
Published: (2023)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
by: Amireddy, Prashanth, et al.
Published: (2025)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)

Trade-offs between Entanglement and Communication
by: Arunachalam, Srinivasan, et al.
Published: (2023)

Distributed inner product estimation with limited quantum communication
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
by: Shpilka, Amir, et al.
Published: (2026)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

On the Complexity of Hazard-Free Formulas
by: Arazi, Leah London, et al.
Published: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)