:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Westover, Alek, Yu, Edward, Zheng, Kai
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2409.10464
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Parity Tests with Ties
by: Kupfer, Ron
Published: (2026)

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

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

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

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

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

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

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

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

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

Sum of Squares Circuits
by: Loconte, Lorenzo, et al.
Published: (2024)

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

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Isomorphism Testing of Rooted Trees in Linear Time
by: Lindeberg, Anna
Published: (2024)

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

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)