# How Hard is it to Find (Honest) Witnesses?

@article{Goldstein2016HowHI, title={How Hard is it to Find (Honest) Witnesses?}, author={Isaac Goldstein and Tsvi Kopelowitz and Moshe Lewenstein and Ely Porat}, journal={ArXiv}, year={2016}, volume={abs/1706.05815} }

In recent years much effort has been put into developing polynomial-time conditional lower bounds for algorithms and data structures in both static and dynamic settings. Along these lines we introduce a framework for proving conditional lower bounds based on the well-known 3SUM conjecture. Our framework creates a compact representation of an instance of the 3SUM problem using hashing and domain specific encoding. This compact representation admits false solutions to the original 3SUM problem… Expand

#### 19 Citations

Conditional Lower Bounds for Space/Time Tradeoffs

- Mathematics, Computer Science
- WADS
- 2017

It is shown that surprisingly many of the well-studied hard problems that are known to have conditional polynomial time lower bounds are also hard when concerning space and this hardness is shown as a tradeoff between the space consumed by the data structure and the time needed to answer queries. Expand

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

- Computer Science
- SODA
- 2019

This work proves that Bellman's 1962 pseudo-polynomial O* (T)-time algorithm for SUBSET SUM on n numbers and target T cannot be improved to time T1-e . Expand

Improved Space-Time Tradeoffs for kSUM

- Computer Science, Mathematics
- ESA
- 2018

An improvement over the best known results for the time-space tradeoff for kSUM is obtained, a major ingredient in achieving these results is a general self-reduction from kSum to mSUM where $m 1$. Expand

All non-trivial variants of 3-LDT are equivalent

- Computer Science, Mathematics
- STOC
- 2020

An efficient deterministic procedure based on the famous Behrend’s construction that partitions a given set of integers into few subsets that avoid a chosen linear equation is used. Expand

Towards Optimal Set-Disjointness and Set-Intersection Data Structures

- Computer Science
- ICALP
- 2020

For online set-disjointness the authors design an algorithm whose runtime, assuming ω = 2 (where ω is the exponent in the fastest matrix multiplication algorithm), matches the lower bound curve of Kopelowitz et al., for q ≤ 1/3 and for set-intersection a conditional lower bound that matches the combinatorial upper bound curve for q ≥ 1/2 is proved. Expand

On problems equivalent to (min, +)-convolution

- Mathematics, Computer Science
- ICALP
- 2017

A systematic study of the (min,+)-convolution problem as a hardness assumption to establish equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. Expand

On Problems Equivalent to (min,+)-Convolution

- Computer Science, Mathematics
- ACM Trans. Algorithms
- 2019

This article establishes the equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences and explains why replacing this assumption with the Strong Exponential Time Hypothesis might not be possible for some problems. Expand

On the Hardness of Set Disjointness and Set Intersection with Bounded Universe

- Computer Science, Mathematics
- ISAAC
- 2019

This paper proves the conditional hardness of SetDisjointness and SetIntersection with bounded universe and presents several applications of these new conditional lower bounds as they exploit the limited universe size. Expand

Text Indexing for Regular Expression Matching

- Computer Science
- Algorithms
- 2021

It is shown that even with arbitrary polynomial preprocessing time, a regular expression query on a text cannot be answered in strongly sublinear time, i.e., O(|T|1−ε) for any ε>0. Expand

ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY

- Mathematics
- Proceedings of the International Congress of Mathematicians (ICM 2018)
- 2019

In recent years, a new “fine-grained” theory of computational hardness has been developed, based on “fine-grained reductions” that focus on exact running times for problems. Mimicking NP-hardness,… Expand

#### References

SHOWING 1-10 OF 26 REFERENCES

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

- Mathematics, Computer Science
- STOC
- 2015

Novel reductions from 3-SUM, APSP, and CNF-SAT are designed, and interesting consequences of this very plausible conjecture are derived, including tight n3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs and new conditional lower bound for the Single-Source-Max-Flow problem. Expand

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

- Mathematics, Computer Science
- 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
- 2014

It is proved that sufficient progress would imply a breakthrough on one of five major open problems in the theory of algorithms, including dynamic versions of bipartite perfect matching, bipartites maximum weight matching, single source reachability, single sources shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems. Expand

Higher Lower Bounds from the 3SUM Conjecture

- Computer Science, Mathematics
- SODA
- 2016

This paper gives new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection and introduces new conditional lower bounds for dynamic versions of Maximum Cardinality Matching, which introduce a new technique for obtaining amortized lower bounds. Expand

Towards polynomial lower bounds for dynamic problems

- Mathematics, Computer Science
- STOC '10
- 2010

This work describes a carefully-chosen dynamic version of set disjointness (the "multiphase problem"), and conjecture that it requires n^Omega(1) time per operation, and forms the first nonalgebraic reduction from 3SUM, which allows3SUM-hardness results for combinatorial problems. Expand

Clustered Integer 3SUM via Additive Combinatorics

- Mathematics, Computer Science
- STOC
- 2015

A collection of new results on problems related to 3SUM are presented, including the first truly subquadratic algorithm for computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n), and preprocessing a binary string for histogram indexing (also called jumbled indexing). Expand

Threesomes, Degenerates, and Love Triangles

- Mathematics, Computer Science
- 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
- 2014

This paper proves that the decision tree complexity of 3SUM is O(n<sup>3/2</sup> √/log n) and proves that improved bounds for k-variate linear degeneracy testing for all odd k ≥ 3 are lead directly to improved bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. Expand

Exact Weight Subgraphs and the k-Sum Conjecture

- Mathematics, Computer Science
- ICALP
- 2013

It is shown that under the k-sum Conjecture, one can achieve tight upper and lower bounds for the Exact-Weight-H problem for various subgraphs H such as matching, star, path, and cycle and that improving on the O(n3) upper bound will imply improved algorithms for 3-sum, 5- sum, All-Pairs Shortest Paths and other fundamental problems. Expand

Faster all-pairs shortest paths via circuit complexity

- Computer Science, Mathematics
- STOC
- 2014

A new randomized method for computing the min-plus product of two n × n matrices is presented, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. Expand

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths

- Computer Science, Mathematics
- ArXiv
- 2014

An odd-looking time complexity solution for binary jumbled pattern matching that improves the state of the art O(n^2/\log^2 n) solutions by more than any poly-logarithmic factor. Expand

On a class of O(n2) problems in computational geometry

- Computer Science
- Comput. Geom.
- 1995

A large class of problems is described for which it is proved that they are all at least as difficult as the following base problem 3sum: Given a set S of n integers, are there three elements of S that sum up to 0. Expand