Cover Image

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dalirrooyfard, Mina, Lincoln, Andrea, Saha, Barna, Williams, Virginia Vassilevska
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

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

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

A Refined Laser Method and Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2020)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

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

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

The Planted Orthogonal Vectors Problem
by: Kühnemann, David, et al.
Published: (2025)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
by: Gupta, Shreya, et al.
Published: (2025)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

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

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Compression of Voxelized Vector Field Data by Boxes is Hard
by: Zhang, Simon
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Online Orthogonal Vectors Revisited
by: Gajulapalli, Karthik, et al.
Published: (2026)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
by: Aggarwal, Divesh, et al.
Published: (2025)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
by: Saha, Barna, et al.
Published: (2024)

Average-Case Reductions for $k$-XOR and Tensor PCA
by: Bresler, Guy, et al.
Published: (2026)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
by: Alman, Josh, et al.
Published: (2025)

It's Hard to HAC with Average Linkage!
by: Bateni, MohammadHossein, et al.
Published: (2024)

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

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Trading Determinism for Time: The k-Reach Problem
by: Bhadra, Ronak, et al.
Published: (2024)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)

Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2026)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

On the Classical Hardness of the Semidirect Discrete Logarithm Problem in Finite Groups
by: Arif, Mohammad Ferry Husnil, et al.
Published: (2025)

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