Document Open Access Logo

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

Authors Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.27.pdf
  • Filesize: 487 kB
  • 16 pages

Document Identifiers

Author Details

Marco L. Carmosino
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Russell Impagliazzo
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Manuel Sabin
  • Computer Science Division, University of California Berkeley, Berkeley, CA, USA

Funding

  • Carmosino, Marco L.: Supported by the Simons Foundation
  • Impagliazzo, Russell: Supported by the Simons Foundation
  • Sabin, Manuel: Supported by the National Science Foundation Graduate Research Fellowship under Grant #DGE-1106400

Cite As Get BibTex

Marco L. Carmosino, Russell Impagliazzo, and Manuel Sabin. Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.27

Abstract

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires n^{epsilon k} time, for some constant epsilon>1/2, to count (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations:
- BPP can be decided in polynomial time using only n^alpha random bits on average over any efficient input distribution, for any constant alpha>0
- BPP can be decided in polynomial time with no randomness on average over the uniform distribution
This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible.
Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Derandomization
  • Hardness vs Randomness
  • Fine-Grained Complexity
  • Average-Case Complexity
  • k-Orthogonal Vectors
  • k-CLIQUE

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 98-117. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.16.
  2. 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. CoRR, abs/1511.06022, 2015. URL: http://arxiv.org/abs/1511.06022.
  3. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 39-51. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_4.
  4. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. URL: http://dx.doi.org/10.1007/BF01275486.
  5. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 81:1-81:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.81.
  6. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51-58. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746612.
  7. Arturs Backurs and Christos Tzamos. Improving viterbi is hard: Better runtimes imply faster clique algorithms. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 311-321. PMLR, 2017. URL: http://proceedings.mlr.press/v70/backurs17a.html.
  8. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 483-496. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055466.
  9. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850-864, 1984. URL: http://dx.doi.org/10.1137/0213053.
  10. Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1), 2006. URL: http://dx.doi.org/10.1561/0400000004.
  11. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: http://dx.doi.org/10.1137/S0097539705446974.
  12. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 307-318. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.36.
  13. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79-97. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.15.
  14. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci., 326(1-3):57-67, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.05.009.
  15. Joan Feigenbaum and Lance Fortnow. On the random-self-reducibility of complete sets. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30 - July 3, 1991, pages 124-132. IEEE Computer Society, 1991. URL: http://dx.doi.org/10.1109/SCT.1991.160252.
  16. Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994-1005, 1993. URL: http://dx.doi.org/10.1137/0222061.
  17. Jiawei Gao and Russell Impagliazzo. Orthogonal vectors is hard for first-order properties on sparse graphs. Electronic Colloquium on Computational Complexity (ECCC), 23:53, 2016. URL: http://eccc.hpi-web.de/report/2016/053.
  18. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2162-2181. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.141.
  19. Oded Goldreich, Hugo Krawczyk, and Michael Luby. On the existence of pseudorandom generators. SIAM J. Comput., 22(6):1163-1175, 1993. URL: http://dx.doi.org/10.1137/0222069.
  20. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 25-32, 1989. URL: http://dx.doi.org/10.1145/73007.73010.
  21. Oded Goldreich and Avi Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In José D. P. Rolim and Salil P. Vadhan, editors, Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings, volume 2483 of Lecture Notes in Computer Science, pages 209-223. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45726-7_17.
  22. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. Uniform hardness vs. randomness tradeoffs for arthur-merlin games. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 33-47. IEEE Computer Society, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214408.
  23. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364-1396, 1999. URL: http://dx.doi.org/10.1137/S0097539793244708.
  24. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672-694, 2002. URL: http://dx.doi.org/10.1016/S0022-0000(02)00024-7.
  25. Russell Impagliazzo and Avi Wigderson. Randomness vs time: Derandomization under a uniform assumption. J. Comput. Syst. Sci., 63(4):672-688, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1780.
  26. Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local reductions. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 749-760. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_61.
  27. Valentine Kabanets. Easiness assumptions and hardness tests: Trading time for zero error. J. Comput. Syst. Sci., 63(2):236-252, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1763.
  28. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: http://dx.doi.org/10.1007/s00037-004-0182-6.
  29. Daniel M. Kane and R. Ryan Williams. The orthogonal vectors conjecture for branching programs and formulas. CoRR, abs/1709.05294, 2017. URL: http://arxiv.org/abs/1709.05294.
  30. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York., The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  31. Jeff Kinne, Dieter van Melkebeek, and Ronen Shaltiel. Pseudorandom generators, typically-correct derandomization, and circuit lower bounds. Computational Complexity, 21(1):3-61, 2012. URL: http://dx.doi.org/10.1007/s00037-011-0019-z.
  32. Richard J. Lipton. New directions in testing. In Joan Feigenbaum and Michael Merritt, editors, Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191-202. DIMACS/AMS, 1989. Google Scholar
  33. Chi-Jen Lu. Derandomizing arthur-merlin games under uniform assumptions. Computational Complexity, 10(3):247-259, 2001. URL: http://dx.doi.org/10.1007/s00037-001-8196-9.
  34. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  35. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80043-1.
  36. Ronen Shaltiel. Weak derandomization of weak algorithms: Explicit versions of yao’s lemma. Computational Complexity, 20(1):87-143, 2011. URL: http://dx.doi.org/10.1007/s00037-011-0006-4.
  37. Ronen Shaltiel and Christopher Umans. Low-end uniform hardness versus randomness tradeoffs for AM. SIAM J. Comput., 39(3):1006-1037, 2009. URL: http://dx.doi.org/10.1137/070698348.
  38. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. URL: http://dx.doi.org/10.1007/s00037-007-0233-x.
  39. Richard Ryan Williams. Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 2:1-2:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.2.
  40. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.023.
  41. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Thore Husfeldt and Iyad A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 17-29. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.17.
  42. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91. IEEE Computer Society, 1982. URL: http://dx.doi.org/10.1109/SFCS.1982.45.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact