The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
A new algorithm for optimal 2-constraint satisfaction and its implications
Open accessOverview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Which Problems Have Strongly Exponential Complexity?
Impagliazzo, R., Paturi, R., & Zane, F. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1774 · Cited by 1,331
Alon, N., Yuster, R., & Zwick, U. (1995) · Journal of the ACM · doi:10.1145/210332.210337 · Cited by 1,002
Exact Algorithms for NP-Hard Problems: A Survey
Woeginger, G. J. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36478-1_17 · Cited by 652
Computing Partitions with Applications to the Knapsack Problem
Horowitz, E., & Sahni, S. K. (1974) · Journal of the ACM · doi:10.1145/321812.321823 · Cited by 605
A probabilistic algorithm for k-SAT and constraint satisfaction problems
Schoning, T. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814612 · Cited by 433
Finding a Minimum Circuit in a Graph
Itai, A., & Rodeh, M. (1978) · SIAM Journal on Computing · doi:10.1137/0207033 · Cited by 391
All pairs shortest paths using bridging sets and rectangular matrix multiplication
Zwick, U. (2002) · Journal of the ACM · doi:10.1145/567112.567114 · Cited by 315
The quadratic assignment problem: A survey and recent developments
Pardalos, P., Rendl, F., & Wolkowicz, H. (1994) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/016/01 · Cited by 294
Partial-Match Retrieval Algorithms
Rivest, R. L. (1976) · SIAM Journal on Computing · doi:10.1137/0205003 · Cited by 244
An improved exponential-time algorithm for k -SAT
Paturi, R., Pudlák, P., Saks, M. E., & Zane, F. (2005) · Journal of the ACM · doi:10.1145/1066100.1066101 · Cited by 209
A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
Schroeppel, R., & Shamir, A. (1981) · SIAM Journal on Computing · doi:10.1137/0210033 · Cited by 204
An improved exponential-time algorithm for k-SAT
Paturi, R., Pudlik, P., Saks, M., & Zane, F. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743513 · Cited by 157
Alon, N., & Naor, M. (1996) · Algorithmica · doi:10.1007/bf01940874 · Cited by 142
New Upper Bounds for Maximum Satisfiability
Niedermeier, R., & Rossmanith, P. (2000) · Journal of Algorithms · doi:10.1006/jagm.2000.1075 · Cited by 107
A Probabilistic 3—SAT Algorithm Further Improved
Hofmeister, T., Schöning, U., Schuler, R., & Watanabe, O. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45841-7_15 · Cited by 101
A New Algorithm for Optimal Constraint Satisfaction and Its Implications
Williams, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27836-8_101 · Cited by 95
Self-citationWorst-case upper bounds for MAX-2-SAT with an application to MAX-CUT
Gramm, J., Hirsch, E. A., Niedermeier, R., & Rossmanith, P. (2003) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(02)00402-x · Cited by 88
An algorithm for the satisfiability problem of formulas in conjunctive normal form
Schuler, R. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.04.012 · Cited by 88
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems
Charikar, M., Indyk, P., & Panigrahy, R. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45465-9_39 · Cited by 49
MAX SAT approximation beyond the limits of polynomial-time approximation
Dantsin, E. Y., Gavrilovich, M., Hirsch, E. A., & Konev, B. Y. (2001) · Annals of Pure and Applied Logic · doi:10.1016/s0168-0072(01)00052-5 · Cited by 47
Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances
Scott, A. D., & Sorkin, G. B. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_32 · Cited by 38
Satisfiability — Algorithms and logic
Pudlák, P. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055762 · Cited by 33
Cell-probe lower bounds for the partial match problem
Jayram, T. S., Khot, S., Kumar, R., & Rabani, Y. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780639 · Cited by 31
Worst-case study of local search for MAX-k-SAT
Hirsch, E. A. (2003) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(02)00404-3 · Cited by 23
On Computing k-CNF Formula Properties
Williams, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24605-3_25 · Cited by 14
Self-citationA 2|E|/4-time algorithm for MAX-CUT
Kulikov, A. S., & Fedin, S. S. (2005) · Journal of Mathematical Sciences · doi:10.1007/s10958-005-0101-7 · Cited by 14
Cited by
Big Bird: Transformers for Longer Sequences
Zaheer, M., Guruganesh, G., Dubey, A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al. (2020) · arXiv · doi:10.48550/arxiv.2007.14062 · Cited by 1,349
Fomin, F. V., & Kratsch, D. (2010) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/978-3-642-16533-7 · Cited by 471
Set Partitioning via Inclusion-Exclusion
Björklund, A., Husfeldt, T., & Koivisto, M. (2009) · SIAM Journal on Computing · doi:10.1137/070683933 · Cited by 370
ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms
Aumüller, M., Bernhardsson, E., & Faithfull, A. (2020) · Information Systems · doi:10.1016/j.is.2019.02.006 · Cited by 300
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
Abboud, A., & Williams, V. V. (2014) · 2014 IEEE 55th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.53 · Cited by 268
Metadata
- Authors
- Williams, R.
- Venue
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2005-12
- Volume
- 348
- Issue
- 2-3
- Pages
- 357-365
- ISSN
- 0304-3975 (ISSN-L)
- OpenAlex
- W2084732238
- Cited by
- 386
- References
- 29
- FWCI
- 15.06
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.