Document Open Access Logo

Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

Authors Dylan M. McKay, Richard Ryan Williams

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2019.56.pdf
  • Filesize: 0.54 MB
  • 20 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Oracles and decision trees
Keywords
  • branching programs
  • random oracles
  • time-space tradeoffs
  • lower bounds
  • SAT
  • counting complexity

Metrics

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

Abstract

We define a model of size-S R-way branching programs with oracles that can make up to S distinct oracle queries over all of their possible inputs, and generalize a lower bound proof strategy of Beame [SICOMP 1991] to apply in the case of random oracles. Through a series of succinct reductions, we prove that the following problems require randomized algorithms where the product of running time and space usage must be Omega(n^2/poly(log n)) to obtain correct answers with constant nonzero probability, even for algorithms with constant-time access to a uniform random oracle (i.e., a uniform random hash function): 
- Given an unordered list L of n elements from [n] (possibly with repeated elements), output [n]-L. 
- Counting satisfying assignments to a given 2CNF, and printing any satisfying assignment to a given 3CNF. Note it is a major open problem to prove a time-space product lower bound of n^{2-o(1)} for the decision version of SAT, or even for the decision problem Majority-SAT. 
- Printing the truth table of a given CNF formula F with k inputs and n=O(2^k) clauses, with values printed in lexicographical order (i.e., F(0^k), F(0^{k-1}1), ..., F(1^k)). Thus we have a 4^k/poly(k) lower bound in this case. 
- Evaluating a circuit with n inputs and O(n) outputs. 
 As our lower bounds are based on R-way branching programs, they hold for any reasonable model of computation (e.g. log-word RAMs and multitape Turing machines).

Cite As Get BibTex

Dylan M. McKay and Richard Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.56

Author Details

Dylan M. McKay
  • EECS and CSAIL, MIT, 32 Vassar St., Cambridge MA, USA
Richard Ryan Williams
  • EECS and CSAIL, MIT, 32 Vassar St., Cambridge MA, USA

Funding

Supported by NSF CCF-1741615 (CAREER: Common Links in Algorithms and Complexity).
  • Williams, Richard Ryan: Parts of this work were performed while visiting the Simons Institute for the Theory of Computing and the EECS department at UC Berkeley.

References

  1. Karl Abrahamson. Generalized string matching. SIAM Journal on Computing, 16(6):1039-1051, 1987. Google Scholar
  2. Karl Abrahamson. Time-space tradeoffs for algebraic problems on general sequential machines. Journal of Computer and System Sciences, 43(2):269-289, 1991. Google Scholar
  3. Miklós Ajtai. Determinism versus nondeterminism for linear time RAMs with memory restrictions. Journal of Computer and System Sciences, 65(1):2-37, 2002. Google Scholar
  4. Miklós Ajtai. A Non-linear Time Lower Bound for Boolean Branching Programs. Theory of Computing, 1(8):149-176, 2005. URL: http://dx.doi.org/10.4086/toc.2005.v001a008.
  5. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  6. David A. Mix Barrington and Pierre McKenzie. Oracle branching programs and Logspace versus P. Information and Computation, 95(1):96-115, 1991. Google Scholar
  7. K. E. Batcher. Sorting Networks and Their Applications. In Proceedings of the April 30-May 2, 1968, Spring Joint Computer Conference, AFIPS '68 (Spring), pages 307-314, 1968. Google Scholar
  8. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM Journal on Computing, 20(2):270-277, 1991. Google Scholar
  9. Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element distinctness, frequency moments, and sliding windows. In FOCS, pages 290-299. IEEE, 2013. Google Scholar
  10. Paul Beame, Thathachar S Jayram, and Michael Saks. Time-space tradeoffs for branching programs. Journal of Computer and System Sciences, 63(4):542-572, 2001. Google Scholar
  11. Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. JACM, 50(2):154-195, 2003. Google Scholar
  12. Paul Beame and Erik Vee. Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. In STOC, pages 688-697. ACM, 2002. Google Scholar
  13. Allan Borodin and Stephen Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 11(2):287-297, 1982. Google Scholar
  14. Samuel R. Buss and Ryan Williams. Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Computational Complexity, 24(3):533-600, 2015. Google Scholar
  15. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 2009. Google Scholar
  16. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  17. Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. JACM, 52(6):835-865, 2005. Google Scholar
  18. Etienne Grandjean. Linear Time Algorithms and NP-Complete Problems. SIAM J. Comput., 23(3):573-597, 1994. Google Scholar
  19. Christian Hoffmann. Exponential Time Complexity of Weighted Counting of Independent Sets. CoRR, abs/1007.1146, 2010. URL: http://arxiv.org/abs/1007.1146.
  20. Richard E Ladner and Nancy A Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10(1):19-32, 1976. Google Scholar
  21. Yishay Mansour, Noam Nisan, and Prasoon Tiwari. The computational complexity of universal hashing. Theoretical Computer Science, 107(1):121-133, 1993. Google Scholar
  22. Jakob Pagter. On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem. Chicago J. Theor. Comput. Sci., 2005. Google Scholar
  23. Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, and William T. Trotter. On Determinism versus Non-Determinism and Related Problems (Preliminary Version). In FOCS, pages 429-438, 1983. Google Scholar
  24. Rahul Santhanam. Lower bounds on the complexity of recognizing SAT by Turing machines. Inf. Process. Lett., 79(5):243-247, 2001. Google Scholar
  25. Martin Sauerhoff and Philipp Woelfel. Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. In STOC, pages 186-195. ACM, 2003. Google Scholar
  26. Dieter van Melkebeek. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science, 2(3):197-303, 2007. Google Scholar
  27. R. Ryan Williams. Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity, 17(2):179-219, 2008. Google Scholar
  28. Ryan Williams. Nonuniform ACC Circuit Lower Bounds. JACM, 61(1):2, 2014. Google Scholar
  29. Andrew C. Yao. Near-optimal time-space tradeoff for element distinctness. In FOCS, pages 91-97, 1988. Google Scholar
  30. Yaacov Yesha. Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer. Journal of Computer and System Sciences, 29(2):183-197, 1984. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact