Buchumschlag

Exponential Separation Between Powers of Regular and General Resolution Over Parities

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharya, Sreejata Kishor, Chattopadhyay, Arkadev, Dvořák, Pavel
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2025)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
von: Bhattacharya, Sreejata Kishor
Veröffentlicht: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
von: Chattopadhyay, Arkadev, et al.
Veröffentlicht: (2025)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
von: Dvořák, Pavel, et al.
Veröffentlicht: (2024)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
von: Czégel, András, et al.
Veröffentlicht: (2025)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
von: Chew, Leroy, et al.
Veröffentlicht: (2024)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
von: Samar, Sahil, et al.
Veröffentlicht: (2026)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
von: Byramji, Farzan, et al.
Veröffentlicht: (2025)

Generalized minimum 0-extension problem and discrete convexity
von: Dvorak, Martin, et al.
Veröffentlicht: (2021)

Parity Tests with Ties
von: Kupfer, Ron
Veröffentlicht: (2026)

On the Complexity of Target Set Selection in Simple Geometric Networks
von: Dvořák, Michal, et al.
Veröffentlicht: (2023)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
von: Gryaznov, Svyatoslav, et al.
Veröffentlicht: (2024)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
von: Yang, Guangxu, et al.
Veröffentlicht: (2026)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
von: Grønlund, Allan, et al.
Veröffentlicht: (2024)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
von: Hitchcock, John M.
Veröffentlicht: (2026)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

The Interplay Between Domination and Separation in Graphs
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2026)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2025)

Exponential lower bound via exponential sums
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2026)

On the Existence of Seedless Condensers: Exploring the Terrain
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2023)

Extractors for Polynomial Sources over $\mathbb{F}_2$
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2023)

Classically Spoofing System Linear Cross Entropy Score Benchmarking
von: Tanggara, Andrew, et al.
Veröffentlicht: (2024)

Constructive Separations and Their Consequences
von: Chen, Lijie, et al.
Veröffentlicht: (2022)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2024)

Black-Box PWPP Is Not Turing-Closed
von: Hubáček, Pavel
Veröffentlicht: (2026)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Separations in Proof Complexity and TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2022)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

Leakage-Resilient Extractors against Number-on-Forehead Protocols
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2025)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
von: Dwivedi, Ashish, et al.
Veröffentlicht: (2024)

A Computational Separation Between Quantum No-cloning and No-telegraphing
von: Nehoran, Barak, et al.
Veröffentlicht: (2023)

Constructive Separations from Gate Elimination
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
von: Li, Zeyong
Veröffentlicht: (2023)

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
von: Gretta, Lucas, et al.
Veröffentlicht: (2026)

Separations between Combinatorial Measures for Transitive Functions
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2021)

Low Degree Local Correction Over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
von: Mukhopadhyay, Partha, et al.
Veröffentlicht: (2025)

Are Depth-2 Regular Expressions Hard to Intersect?
von: Ascone, Rocco, et al.
Veröffentlicht: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
von: Bhattacharjee, Sutanay, et al.
Veröffentlicht: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
von: Jackson, Andrew
Veröffentlicht: (2025)