Copertina

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gryaznov, Svyatoslav, Ovcharov, Sergei, Riazanov, Artur
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
di: Gryaznov, Svyatoslav, et al.
Pubblicazione: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
di: Glinskih, Ludmila, et al.
Pubblicazione: (2024)

Better Boosting of Communication Oracles, or Not
di: Harms, Nathaniel, et al.
Pubblicazione: (2024)

Equality is Far Weaker than Constant-Cost Communication
di: Göös, Mika, et al.
Pubblicazione: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
di: Göös, Mika, et al.
Pubblicazione: (2023)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
di: Riazanov, Artur, et al.
Pubblicazione: (2025)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Pseudodeterministic Communication Complexity
di: Göös, Mika, et al.
Pubblicazione: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2026)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Sampling Permutations with Cell Probes is Hard
di: Alekseev, Yaroslav, et al.
Pubblicazione: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
di: Jackson, Andrew
Pubblicazione: (2025)

Proving Unsatisfiability with Hitting Formulas
di: Filmus, Yuval, et al.
Pubblicazione: (2023)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
di: Bhattacharya, Sreejata Kishor, et al.
Pubblicazione: (2024)

Quasi-Linear Size PCPs with Small Soundness from HDX
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
di: Berkholz, Christoph, et al.
Pubblicazione: (2024)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
di: Bhangale, Amey, et al.
Pubblicazione: (2026)

Solving Polynomial Equations Over Finite Fields
di: Dell, Holger, et al.
Pubblicazione: (2024)

On the Complexity of Combinatorial Optimization on Fixed Structures
di: Megiddo, Nimrod
Pubblicazione: (2024)

Separations between Combinatorial Measures for Transitive Functions
di: Chakraborty, Sourav, et al.
Pubblicazione: (2021)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
di: Yamakami, Tomoyuki
Pubblicazione: (2017)

Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
di: Conrado, Giovanna K., et al.
Pubblicazione: (2023)

Computational Complexity of Game Boy Games
di: Tirmazi, Hayder, et al.
Pubblicazione: (2024)

Isomorphism Testing of Rooted Trees in Linear Time
di: Lindeberg, Anna
Pubblicazione: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
di: Wang, Qisheng, et al.
Pubblicazione: (2024)

Game Derandomization
di: Epstein, Samuel
Pubblicazione: (2024)

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

Sorting by pile shuffles on queue-like and stack-like piles can be hard
di: Treleaven, Kyle B.
Pubblicazione: (2025)

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

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

Combinatorial refinement on circulant graphs
di: Kluge, Laurence
Pubblicazione: (2022)

Linear Equations with Min and Max Operators: Computational Complexity
di: Chatterjee, Krishnendu, et al.
Pubblicazione: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
di: Bortolotti, Alex, et al.
Pubblicazione: (2025)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

On the Smoothed Complexity of Combinatorial Local Search
di: Giannakopoulos, Yiannis, et al.
Pubblicazione: (2022)

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

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
di: Cai, Jin-Yi, et al.
Pubblicazione: (2025)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
di: Hitchcock, John M.
Pubblicazione: (2026)