A new algorithm for optimal 2-constraint satisfaction and its implications

By Ryan Williams. 2005

546 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Algorithms & Complexity

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, background): “The impossibility for sparse-attention follows from hardness results stemming from Orthogonal Vector Conjecture(OVC) [1, 2, 7, 97].”
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (2014, methodology): “4 The ﬁrst step of our reduction mimics the approaches in [Bri14] and [AWW14] and is based on the split and list technique of [Wil05].”
Set Partitioning via Inclusion-Exclusion (2009, unknown): “, Williams [47] and Koivisto [33].”
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, unknown): “and subset query problems [38], [39], [30].”
On The Computational Complexity of Self-Attention (2022, background): “The Strong Exponential Time Hypothesis (SETH) [33, 34] Previous work has that for all ǫ > 0 , there is no O ( n 2 − ǫ ) algorithm solves OVP for d = ω (log n ) unless SETH is false [41].”
Exact exponential algorithms (2010, methodology): “The following approach for doing this is due to Williams.(36) An alternative approach via sum-product algorithms is due to Koivisto.”
Consequences of Faster Alignment of Sequences (2014, methodology): “Williams [57] proved that a similar problem requires n1−o(1) query time if allowed O(n2−ε) preprocessing time, under Strong ETH.”
Tight Hardness Results for LCS and Other Sequence Similarity Measures (2015, methodology): “We will base our results on the following conjecture, which is possibly more plausible than SETH: it is known to be implied by SETH (follows from [48]), yet might still be true even if SETH turns out to be false.”
Computing branchwidth via efficient triangulations and blocks (2005, unknown): “hal-00390623, version 1 - 2 Jun 2009 Maximum Independent Set [20,28,12], (Maximum) Satisability [9,19,25,29, 32 ], Coloring [2,6], and many others (see the recent survey written by Woeginger [33] for an overview).”
ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms (2018, background): “A phenomenon called the curse of dimensionality , a consequence of several popular algorithmic hardness conjectures (see [4, 38]), tells us that, to obtain the true nearest neighbors, we have to use either linear time (in the size of the dataset) or time/space that is exponential in the…”