Imagen de Portada

Direct Sums for Parity Decision Trees

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Besselman, Tyler, Göös, Mika, Guo, Siyao, Maystre, Gilbert, Yuan, Weiqiang
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity F.2.2; F.2.3
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Supercritical Tradeoffs for Monotone Circuits
por: Göös, Mika, et al.
Publicado: (2024)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
por: van Brügge, Jan
Publicado: (2024)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
por: de Rezende, Susanna F., et al.
Publicado: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
por: de Rezende, Susanna F., et al.
Publicado: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
por: Conneryd, Jonas, et al.
Publicado: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
por: Håstad, Johan, et al.
Publicado: (2022)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
por: de Rezende, Susanna F., et al.
Publicado: (2019)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
por: Antonelli, Melissa, et al.
Publicado: (2025)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
por: Salas, Jesus
Publicado: (2025)

On the Complexity of Determinations
por: Hellerstein, Joseph M.
Publicado: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
por: Conneryd, Jonas, et al.
Publicado: (2025)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
por: Burke, Kyle, et al.
Publicado: (2024)

Thin Tree Verification is coNP-Complete
por: Moayyedi, Alice
Publicado: (2025)

Limitation of Quantum Walk Approach to the Maximum Matching Problem
por: Júnior, Alcides Gomes Andrade, et al.
Publicado: (2025)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
por: Kowaluk, Miroslaw, et al.
Publicado: (2025)

Fast Simulation of Cellular Automata by Self-Composition
por: Natal, Joseph, et al.
Publicado: (2024)

A Polynomial Time Algorithm for 3SAT
por: Quigley, Robert
Publicado: (2024)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
por: Kiatchaipipat, Nattapol, et al.
Publicado: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
por: Fritsch, Timo, et al.
Publicado: (2026)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
por: Gupta, Chetan, et al.
Publicado: (2025)

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

Algorithmic Trading Strategy Development and Optimisation
por: Yuan, Owen Nyo Wei, et al.
Publicado: (2026)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
por: Saha, Barna, et al.
Publicado: (2024)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
por: Shalaby, Ahmed, et al.
Publicado: (2024)

Min-CSPs on Complete Instances
por: Anand, Aditya, et al.
Publicado: (2024)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
por: Knop, Dušan, et al.
Publicado: (2017)

On the Satisfaction Probabilities of $k$-CNF Formulas
por: Tantau, Till
Publicado: (2022)

Battle Sheep is PSPACE-complete
por: Burke, Kyle, et al.
Publicado: (2025)

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

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

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
por: Asadi, Ali, et al.
Publicado: (2025)

Proving Unsatisfiability with Hitting Formulas
por: Filmus, Yuval, et al.
Publicado: (2023)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
por: Dvořák, Pavel, et al.
Publicado: (2017)

Quantum algorithms through graph composition
por: Cornelissen, Arjan
Publicado: (2025)

Quantum walks through generalized graph composition
por: Cornelissen, Arjan
Publicado: (2025)

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

Quantum Sabotage Complexity
por: Cornelissen, Arjan, et al.
Publicado: (2024)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
por: Lingas, Andrzej
Publicado: (2026)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
por: Bartlett, Celina Janet
Publicado: (2025)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
por: Bodirsky, Manuel, et al.
Publicado: (2026)