Imagen de Portada

New Direct Sum Tests

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Westover, Alek, Yu, Edward, Zheng, Kai
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
por: Liu, Brian, et al.
Publicado: (2024)

A Strong Direct Sum Theorem for Distributional Query Complexity
por: Blanc, Guy, et al.
Publicado: (2024)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
por: Mackenzie, Simon, et al.
Publicado: (2024)

Characterizing Direct Product Testing via Coboundary Expansion
por: Bafna, Mitali, et al.
Publicado: (2023)

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

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

Geometry Of The Subset Sum Problem -- Part I
por: Bollepalli, Srinivas Balaji
Publicado: (2025)

Direct Product Primality Testing of Graphs is GI-hard
por: Calderoni, Luca, et al.
Publicado: (2020)

Direct Sums for Parity Decision Trees
por: Besselman, Tyler, et al.
Publicado: (2024)

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

Lower Bounds for Subset Sum in Resolution with Modular Counting
por: Part, Fedor
Publicado: (2022)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
por: Kocurek, Nicholas
Publicado: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
por: Nkosi, Thami
Publicado: (2025)

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
por: Rossman, Benjamin, et al.
Publicado: (2025)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

A Subexponential Reduction from Product Partition to Subset Sum
por: Costandin, Marius
Publicado: (2024)

On the Degree Automatability of Sum-of-Squares Proofs
por: Bortolotti, Alex, et al.
Publicado: (2025)

Optimization of a Quantum Subset Sum Oracle
por: Benoit, Angelo, et al.
Publicado: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
por: Gur, Tom, et al.
Publicado: (2025)

Improved Space Bounds for Subset Sum
por: Belova, Tatiana, et al.
Publicado: (2024)

On the Parameterized Complexity of Min-Sum-Radii
por: Kumar, Pankaj, et al.
Publicado: (2026)

Parity Tests with Ties
por: Kupfer, Ron
Publicado: (2026)

Direct Product Theorems for Randomized Query Complexity
por: Ben-David, Shalev, et al.
Publicado: (2025)

Does Subset Sum Admit Short Proofs?
por: Włodarczyk, Michał
Publicado: (2024)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
por: Gordeev, Lev, et al.
Publicado: (2026)

Biased Linearity Testing in the 1% Regime
por: Khot, Subhash, et al.
Publicado: (2025)

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

On Matrix Multiplication and Polynomial Identity Testing
por: Andrews, Robert
Publicado: (2022)

A Parameterized Study of Secluded Structures in Directed Graphs
por: Schmidt, Jonas, et al.
Publicado: (2025)

On the Relationship Between Several Variants of the Linear Hashing Conjecture
por: Westover, Alek
Publicado: (2023)

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
por: Minzer, Dor, et al.
Publicado: (2025)

Subset Balancing and Generalized Subset Sum via Lattices
por: Gao, Yiming, et al.
Publicado: (2026)

Isomorphism Testing of Rooted Trees in Linear Time
por: Lindeberg, Anna
Publicado: (2024)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
por: Ramya, C., et al.
Publicado: (2025)

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

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
por: Bhattacharjee, Sutanay, et al.
Publicado: (2026)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
por: Sajith, Thejas Radhika
Publicado: (2025)

Collapsing Catalytic Classes
por: Koucký, Michal, et al.
Publicado: (2025)

Quantum Property Testing for Bounded-Degree Directed Graphs
por: Peng, Pan, et al.
Publicado: (2026)

A Note on the Complexity of Directed Clique
por: Gutowski, Grzegorz, et al.
Publicado: (2026)