Fetching the paper…
Reading the bibliography…
We present a new distributed model of probabilistically checkable proofs (PCP).
Behnam Neyshabur and Nathan Srebro, On symmetric and asymmetric lshs for inner product search , Proc. of the 32nd International Conference on Machine Learning, ICML, 2015, pp. 1926–1934
1934
Earlier work this paper cites.
Ken Thompson, Programming techniques: Regular expression search algorithm , Communications of the ACM 11
1968
Earlier work this paper cites.
Ronald Linn Rivest, Analysis of associative retrieval algorithms. , Ph.D. thesis, Stanford University, Stanford, CA, USA, 1974, AAI7420230
1974
Earlier work this paper cites.
Ronald L Rivest, Partial-match retrieval algorithms , SIAM Journal on Computing 5
1976
Earlier work this paper cites.
Ömer Egecioglu and Bahman Kalantari, Approximating the diameter of a set of points in the euclidean space , Inf. Process. Lett. 32
1989
Earlier work this paper cites.
Eugene W Myers and Webb Miller, Approximate matching of regular expressions , Bulletin of mathematical biology 51
1989
Earlier work this paper cites.
Bala Kalyanasundaram and Georg Schnitger, The probabilistic communication complexity of set intersection , SIAM J. Discrete Math. 5
1992
Earlier work this paper cites.
Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan, Algebraic methods for interactive proof systems , J. ACM 39
1992
Earlier work this paper cites.
Gene Myers, A four russians algorithm for regular expression pattern matching , Journal of the ACM (JACM) 39
1992
Earlier work this paper cites.
Alexander A. Razborov, On the distributional complexity of disjointness , Theor. Comput. Sci. 106
1992
Earlier work this paper cites.
Anka Gajentaan and Mark H. Overmars, On a class of o(n2) problems in computational geometry , Comput. Geom. 5
1995
Earlier work this paper cites.
Mauricio Karchmer, Eyal Kushilevitz, and Noam Nisan, Fractional covers and communication complexity , SIAM J. Discrete Math. 8
1995
Earlier work this paper cites.
James R Knight and Eugene W Myers, Approximate regular expression pattern matching with concave gap penalties , Algorithmica 14
1995
Earlier work this paper cites.
Sun Wu, Udi Manber, and Eugene Myers, A subquadratic algorithm for approximate regular expression matching , Journal of algorithms 19
1995
Earlier work this paper cites.
Andrei Z Broder, Steven C Glassman, Mark S Manasse, and Geoffrey Zweig, Syntactic clustering of the web , Computer Networks and ISDN Systems 29
1997
Earlier work this paper cites.
Andrei Z Broder, On the resemblance and containment of documents , Compression and Complexity of Sequences 1997. Proceedings, IEEE, 1997, pp. 21–29
1997
Earlier work this paper cites.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, Proof verification and the hardness of approximation problems , J. ACM 45
1998
Earlier work this paper cites.
Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: A new characterization of NP , J. ACM 45
1998
Earlier work this paper cites.
Harry Buhrman, Richard Cleve, and Avi Wigderson, Quantum vs. classical communication and computation , Proc. of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998, pp. 63–68
1998
Earlier work this paper cites.
Piotr Indyk and Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality , Proc. of the thirtieth annual ACM symposium on Theory of computing, ACM, 1998, pp. 604–613
1998
Earlier work this paper cites.
Piotr Indyk, On approximate nearest neighbors in non-euclidean spaces , 39th Annual Symposium on Foundations of Computer Science, FOCS, 1998, pp. 148–155
1998
Earlier work this paper cites.
Gad M Landau, Eugene W Myers, and Jeanette P Schmidt, Incremental string comparison , SIAM Journal on Computing 27
1998
Earlier work this paper cites.
Eugene Myers, Paulo Oliva, and Katia Guimarães, Reporting exact and approximate regular expression matches , Combinatorial pattern matching, Springer, 1998, pp. 91–103
1998
Earlier work this paper cites.
Ran Raz, A parallel repetition theorem , SIAM J. Comput. 27
1998
Earlier work this paper cites.
Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication) , SIAM J. Comput. 28
1999
Earlier work this paper cites.
Karthikeyan Ramasamy, Jignesh M Patel, Jeffrey F Naughton, and Raghav Kaushik, Set containment joins: The good, the bad and the ugly. , VLDB, 2000, pp. 351–362
2000
Earlier work this paper cites.
Graham Cormode, S Muthukrishnan, and Süleyman Cenk Sahinalp, Permutation editing and matching via embeddings , International Colloquium on Automata, Languages, and Programming, Springer, 2001, pp. 481–492
2001
Earlier work this paper cites.
Ashish Goel, Piotr Indyk, and Kasturi R. Varadarajan, Reductions among high dimensional proximity problems , Proc. of the Twelfth Annual Symposium on Discrete Algorithms, 2001, pp. 769–778
2001
Earlier work this paper cites.
Johan Håstad, Some optimal inapproximability results , J. ACM 48
2001
Earlier work this paper cites.
Russell Impagliazzo and Ramamohan Paturi, On the complexity of k-sat , J. Comput. Syst. Sci. 62
2001
Earlier work this paper cites.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, Which problems have strongly exponential complexity? , J. Comput. Syst. Sci. 63
2001
Earlier work this paper cites.
Daniele V. Finocchiaro and Marco Pellegrini, On computing the diameter of a point set in high dimensional euclidean space , Theor. Comput. Sci. 287
2002
Earlier work this paper cites.
Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova, Lower bounds for embedding edit distance into normed spaces , Proc. of the 14th SODA, 2003, pp. 523–526
2003
Earlier work this paper cites.
Sergey Melnik and Hector Garcia-Molina, Adaptive algorithms for set containment joins , ACM Transactions on Database Systems (TODS) 28
2003
Earlier work this paper cites.
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar, An information statistics approach to data stream and communication complexity , J. Comput. Syst. Sci. 68
2004
Earlier work this paper cites.
Allan Borodin, Rafail Ostrovsky, and Yuval Rabani, Subquadratic approximation algorithms for clustering problems in high dimensional spaces , Machine Learning 56
2004
Earlier work this paper cites.
Ziv Bar-Yossef, TS Jayram, Robert Krauthgamer, and Ravi Kumar, Approximating edit distance efficiently , Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, IEEE, 2004, pp. 550–559
2004
Earlier work this paper cites.
Gonzalo Navarro, Approximate regular expression searching with arbitrary integer weights. , Nord. J. Comput. 11
2004
Earlier work this paper cites.
S Cenk Sahinalp and Andrey Utis, Hardness of string similarity search and other indexing problems , International Colloquium on Automata, Languages, and Programming, Springer, 2004, pp. 1080–1098
2004
Earlier work this paper cites.
Graham Cormode and S. Muthukrishnan, Space efficient mining of multigraph streams , Proc. of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005, pp. 271–282
2005
Earlier work this paper cites.
Subhash Khot and Assaf Naor, Nonembeddability theorems via fourier analysis , Proc. of the 46th FOCS, IEEE, 2005, pp. 101–110
2005
Earlier work this paper cites.
R. Ryan Williams, A new algorithm for optimal 2 2 -constraint satisfaction and its implications , Theoretical Computer Science 348
2005
Earlier work this paper cites.
Alexandr Andoni and Piotr Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions , Proc. of the 47th FOCS, IEEE, 2006, pp. 459–468
2006
Cited alongside, same era.
Alexandr Andoni, Piotr Indyk, and Mihai Patrascu, On the optimality of the dimensionality reduction method , Proc. of the 47th FOCS, IEEE, 2006, pp. 449–458
2006
Cited alongside, same era.
Tuğkan Batu, Funda Ergun, and Cenk Sahinalp, Oblivious string embeddings and edit distance approximations , Proc. of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, Society for Industrial and Applied Mathematics, 2006, pp. 792–801
2006
Cited alongside, same era.
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi, A duality between clause width and clause density for SAT , Proc. of 21st Conference on Computational Complexity (CCC), 2006, pp. 252–260
2006
Cited alongside, same era.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt, Practical and optimal lsh for angular distance , Advances in Neural Information Processing Systems, 2015, pp. 1225–1233
2015
Later among the works it cites.
Alexandr Andoni and Ilya Razenshteyn, Optimal data-dependent hashing for approximate near neighbors , Proc. of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, ACM, 2015, pp. 793–801
2015
Later among the works it cites.
Amirali Abdullah and Suresh Venkatasubramanian, A directed isoperimetric inequality with application to bregman near neighbor lower bounds , Proc. of the 47th STOC, ACM, 2015, pp. 509–518
2015
Later among the works it cites.
Josh Alman and Ryan Williams, Probabilistic polynomials and hamming nearest neighbors , Proc. of the 56th FOCS, IEEE, 2015, pp. 136–150
2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Alexandr Andoni and Robert Krauthgamer, The computational hardness of estimating edit distance [extended abstract] , Proc. of the 48th FOCS, 2007, pp. 724–734
2007
Cited alongside, same era.
Irit Dinur, The PCP theorem by gap amplification , J. ACM 54
2007
Cited alongside, same era.
Rajeev Motwani, Assaf Naor, and Rina Panigrahy, Lower bounds on locality sensitive hashing , SIAM Journal on Discrete Mathematics 21
2007
Cited alongside, same era.
Rafail Ostrovsky and Yuval Rabani, Low distortion embeddings for edit distance , Journal of the ACM (JACM) 54
2007
Cited alongside, same era.
Ali Rahimi, Benjamin Recht, et al., Random features for large-scale kernel machines. , NIPS, vol. 3, 2007, p. 5
2007
Cited alongside, same era.
Alexandr Andoni, Dorian Croitoru, and Mihai Patrascu, Hardness of nearest neighbor under l-infinity , Proc. of the 49th FOCS, 2008, pp. 424–433
2008
Cited alongside, same era.
Yael Tauman Kalai and Ran Raz, Interactive PCP , Automata, Languages and Programming, 35th International Colloquium, ICALP, 2008, pp. 536–547
2008
Cited alongside, same era.
Rina Panigrahy, Kunal Talwar, and Udi Wieder, A geometric approach to lower bounds for approximate near-neighbor search and partial match , Proc. of the 49th FOCS, IEEE, 2008, pp. 414–423
2008
Cited alongside, same era.
Surender Baswana, Manoj Gupta, and Sandeep Sen, Fully dynamic maximal matching in o( \ \backslash logn) update time , SIAM Journal on Computing 44
2015
Later among the works it cites.
Arturs Backurs and Piotr Indyk, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) , Proc. of the 47th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2015, pp. 51–58
2015
Later among the works it cites.
Karl Bringmann and Marvin Kunnemann, Quadratic conditional lower bounds for string problems and dynamic time warping , Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2015, pp. 79–97
2015
Later among the works it cites.
2015
Later among the works it cites.
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum, Delegating computation: Interactive proofs for muggles , J. ACM 62
2015
Later among the works it cites.
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak, Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture , Proc. of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, 2015, pp. 21–30
2015
Later among the works it cites.
Gregory Valiant, Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem , Journal of the ACM (JACM) 62
2015
Later among the works it cites.
Virginia Vassilevska Williams, Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk) , LIPIcs-Leibniz International Proceedings in Informatics, vol. 43, 2015
2015
Later among the works it cites.
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams, Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made , Proc. of the 48th STOC, 2016, pp. 375–388
2016
Later among the works it cites.
Thomas Dybdahl Ahle, Rasmus Pagh, Ilya Razenshteyn, and Francesco Silvestri, On the complexity of inner product similarity join , Proc. of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ACM, 2016, pp. 151–164
2016
Later among the works it cites.
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner, Short interactive oracle proofs with constant query complexity, via composition and sumcheck , IACR Cryptology ePrint Archive 2016
2016
Later among the works it cites.
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner, Interactive oracle proofs , Theory of Cryptography - 14th International Conference, TCC, 2016, pp. 31–60
2016
Later among the works it cites.
2016
Later among the works it cites.
Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai, New deterministic approximation algorithms for fully dynamic matching , Proc. of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2016, pp. 398–411
2016
Later among the works it cites.
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth, Constant rate pcps for circuit-sat with sublinear query complexity , J. ACM 63
2016
Later among the works it cites.
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström, On problems as hard as CNF-SAT , ACM Transactions on Algorithms 12
2016
Later among the works it cites.
2016
Later among the works it cites.
Søren Dahlgaard, On the hardness of partially dynamic graph problems and connections to diameter , Proc. of the 43rd ICALP, 2016, pp. 48:1–48:14
2016
Later among the works it cites.
2016
Later among the works it cites.
Matti Karppa, Petteri Kaski, and Jukka Kohonen, A faster subquadratic algorithm for finding outlier correlations , Proc. of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2016, pp. 1288–1305
2016
Later among the works it cites.
Tsvi Kopelowitz, Seth Pettie, and Ely Porat, Higher lower bounds from the 3sum conjecture , Proc. of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2016, pp. 1272–1287
2016
Later among the works it cites.
Daniel Moeller, Ramamohan Paturi, and Stefan Schneider, Subquadratic algorithms for succinct stable matching , International Computer Science Symposium in Russia, Springer, 2016, pp. 294–308
2016
Later among the works it cites.
Ofer Neiman and Shay Solomon, Simple deterministic algorithms for fully dynamic maximal matching , ACM Transactions on Algorithms (TALG) 12
2016
Later among the works it cites.
David Peleg and Shay Solomon, Dynamic (1+ ε \varepsilon )-approximate matchings: a density-sensitive approach , Proc. of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2016, pp. 712–729
2016
Later among the works it cites.
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum, Constant-round interactive proofs for delegating computation , Proc. of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2016, pp. 49–62
2016
Later among the works it cites.
Shay Solomon, Fully dynamic maximal matching in constant update time , Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, IEEE, 2016, pp. 325–334
2016
Later among the works it cites.
Christina Teflioudi and Rainer Gemulla, Exact and approximate maximum inner product search with lemp , ACM Transactions on Database Systems (TODS) 42
2016
Later among the works it cites.
Richard Ryan Williams, Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation , 31st Conference on Computational Complexity, CCC, 2016, pp. 2:1–2:17
2016
Later among the works it cites.
Amir Abboud and Arturs Backurs, Towards hardness of approximation for polynomial time problems , ITCS, to appear, 2017
2017
Closest in time.
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten, Optimal hashing-based time-space trade-offs for approximate near neighbors , Proc. of the 28th SODA, 2017, pp. 47–66
2017
Closest in time.
Amir Abboud, Aviad Rubinstein, and Ryan Williams, Distributed PCP Theorems for Hardness of Approximation in P , FOCS, to appear, 2017
2017
Closest in time.
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan, Average-case fine-grained hardness , IACR Cryptology ePrint Archive 2017
2017
Closest in time.
Tobias Christiani, A framework for similarity search with space-time tradeoffs using locality-sensitive filtering , Proc. of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2017, pp. 31–46
2017
Closest in time.
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams, Completeness for first-order properties on sparse structures with algorithmic applications , Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, pp. 2162–2181
2017
Closest in time.
Kasper Green Larsen and R. Ryan Williams, Faster online matrix-vector multiplication , Proc. of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2017, pp. 2182–2189
2017
Closest in time.
Omer Reingold, March 2017, Private Communication
2017
Closest in time.
Ryan Williams, On the complexity of furthest, closest, and orthogonal pairs in low dimensions , SODA, to appear, 2018
2018
Closest in time.