article

Time-space trade-off lower bounds for randomized computation of decision problems

Authors:

Erik VeeAuthors Info & Claims

Journal of the ACM (JACM), Volume 50, Issue 2

Pages 154 - 195

https://doi.org/10.1145/636865.636867

Published: 01 March 2003 Publication History

Abstract

We prove the first time-space lower bound trade-offs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are extension of those used by Ajtai and by Beame, Jayram, and Saks that applied to deterministic branching programs. Our results also give a quantitative improvement over the previous results.Previous time-space trade-off results for decision problems can be divided naturally into results for functions with Boolean domain, that is, each input variable is {0,1}-valued, and the case of large domain, where each input variable takes on values from a set whose size grows with the number of variables.In the case of Boolean domain, Ajtai exhibited an explicit class of functions, and proved that any deterministic Boolean branching program or RAM using space S = o(n) requires superlinear time T to compute them. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives T = Ω(n log log n/log log log n) for S = O(n^1-ϵ). For the same functions considered by Ajtai, we prove a time-space trade-off (for randomized branching programs with error) of the form T = Ω(n √ log(n/S)/log log (n/S)). In particular, for space O(n^1-ϵ), this improves the lower bound on time to Ω(n√ log n/log log n).In the large domain case, we prove lower bounds of the form T = Ω(n√ log(n/S)/log log (n/S)) for randomized computation of the element distinctness function and lower bounds of the form T = Ω(n log (n/S)) for randomized computation of Ajtai's Hamming closeness problem and of certain functions associated with quadratic forms over large fields.

References

[1]

Abrahamson, K. R. 1990. A time-space tradeoff for Boolean matrix multiplication. In Proceedings 31st Annual Symposium on Foundations of Computer Science. (St. Louis, Mo.) IEEE Computer Society Press, Los Alamitos, Calif., 412--419.

Digital Library

[2]

Abrahamson, K. R. 1991. Time--space trade-offs for algebraic problems on general sequential models. J. Comput. Syst. Sci. 43, 2 (Oct.), 269--289.

Digital Library

[3]

Ajtai, M. 1999a. Determinism versus non-determinism for linear time RAMs with memory restrictions. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga.). ACM, New York, 632--641.

Digital Library

[4]

Ajtai, M. 1999b. A non-linear time lower bound for boolean branching programs. In Proceedings 40th Annual Symposium on Foundations of Computer Science (New York, N.Y.) IEEE Computer Society Press, Los Alamitos, Calif., 60--70.

Digital Library

[5]

Ajtai, M. 2002. Determinism versus non-determinism for linear time RAMs with memory restrictions. J. Comput. Syst. Sci. 65, 1 (Aug.), 2--37.

Digital Library

[6]

Alon, N., and Maass, W. 1988. Meanders and their applications in lower bounds arguments. J. Comput. Syst. Sci. 37, 118--129.

Digital Library

[7]

Babai, L., Frankl, P., and Simon, J. 1986. Complexity classes in communication complexity theory. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science. (Toronto, Ontario, Canada). IEEE Computer Society Press, Los Alamitos, Calif., 337--347.

[8]

Babai, L., Nisan, N., and Szegedy, M. 1992. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci. 45, 2 (Oct.), 204--232.

Digital Library

[9]

Beame, P., Jayram, T. S., and Saks, M. 2001. Time-space trade-offs for branching programs. J. Comput. Syst. Sci. 63, 4 (Dec.), 542--572.

Digital Library

[10]

Beame, P., and Vee, E. 2002. Time-space trade-offs, multiparty communication complexity, and nearest-neighbor problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, (Montreal, Quebec, Canada). ACM, New York, 688--697.

Digital Library

[11]

Beame, P. W. 1991. A general time-space tradeoff for finding unique elements. SIAM J. Comput. 20, 2, 270--277.

Digital Library

[12]

Beame, P. W., Saks, M., and Thathachar, J. S. 1998. Time-space trade-offs for branching programs. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Palo Alto, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 254--263.

Digital Library

[13]

Borodin, A. 1993. Time space trade-offs (getting closer to the barrier?). In Proceedings of the 4th International Symposium on Algorithms and Computation (Hong Kong). 209--220.

Digital Library

[14]

Borodin, A., and Cook, S. A. 1982. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing 11, 2 (May), 287--297.

[15]

Borodin, A., Fich, F. E., Meyer auf der Heide, F., Upfal, E., and Wigderson, A. 1987. A time-space tradeoff for element distinctness. SIAM J. Comput. 16, 1 (Feb.), 97--99.

Digital Library

[16]

Borodin, A., Fischer, M. J., Kirkpatrick, D. G., Lynch, N. A., and Tompa, M. 1981. A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst. Sci. 22, 3 (June), 351--364.

[17]

Borodin, A., Razborov, A. A., and Smolensky, R. 1993. On lower bounds for read-k times branching programs. Comput. Complex. 3, 1--18.

Digital Library

[18]

Fortnow, L. 1997. Nondeterministic polynomial time versus nondeterministic logarithmic space: Time-space trade-offs for satisfiability. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (formerly: Structure in Complexity Theory Conference) (Ulm, Germany) IEEE Computer Society Press, Los Alamitos, Calif., 52--60.

Digital Library

[19]

Fortnow, L., and van Melkebeek, D. 2000. Time-space trade-offs for nondeterministic computation. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity (Florence, Italy,) IEEE Computer Society Press, Los Alamitos, Calif., 2--13.

Digital Library

[20]

Hardy, G. H., Littlewood, J. E., and Polya, G. 1952. Inequalities. Cambridge University Press.

[21]

Harper, L. 1966. Optimal numberings and isoperimetric problems on graphs. J. Combinat. Theory 1, 385--394.

[22]

Kalyanasundaram, B., and Schnitger, G. 1987. The probabilistic communication complexity of set intersection. In Proceedings, 2nd Annual Conference on Structure in Complexity Theory, (Cornell University, Ithaca, N.Y.) IEEE Computer Society Press, Los Alamitos, Calif., 41--49.

[23]

Kushilevitz, E., and Nisan, N. 1997. Communication Complexity. Cambridge University Press, Cambridge {England} ; New York.

Digital Library

[24]

Lipton, R., and Viglas, A. 1999. Time-space trade-offs for SAT. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (New York, N.Y.) IEEE Computer Society Press, Los Alamitos, Calif., 459--464.

Digital Library

[25]

Mansour, Y., Nisan, N., and Tiwari, P. 1993. The computational complexity of universal hashing. Theoret. Comput. Sci. 107, 121--133.

Digital Library

[26]

Okol'nishnikova, E. 1993. On lower bounds for branching programs. Sib. Adv. Math. 3, 1, 152--166.

[27]

Pagter, J. 2001. Time-Space Tradeoffs. Ph.D. thesis, BRICS.

[28]

Razborov, A. A. 1990. On the distributional complexity of disjointness. In Automata, Languages, and Programming: 17th International Colloquium, (Warwick University, England). M. S. Paterson, Ed. Lecture Notes in Computer Science, vol. 443. Springer-Verlag, New York, 249--253.

Digital Library

[29]

Yao, A. C. 1988. Near-optimal time-space tradeoff for element distinctness. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (White Plains, N.Y.) IEEE Computer Society Press, Los Alamitos, Calif., 91--97.

Digital Library

Cited By

Hamoudi YMagniez F(2023)Quantum Time–Space Tradeoff for Finding Multiple Collision PairsACM Transactions on Computation Theory10.1145/358998615:1-2(1-22)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3589986
Cook SMcKenzie PWehr DBraverman MSanthanam R(2023)Pebbles and Branching Programs for Tree EvaluationLogic, Automata, and Computational Complexity10.1145/3588287.3588303(261-318)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588287.3588303
Williams R(2022)Some Estimated Likelihoods for Computational ComplexityComputing and Software Science10.1007/978-3-319-91908-9_2(9-26)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-91908-9_2
Show More Cited By

Index Terms

Time-space trade-off lower bounds for randomized computation of decision problems
1. Theory of computation

Recommendations

Time-space trade-offs for predecessor search
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an ...
Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Near-Optimal Time-Space Tradeoff for Element Distinctness

It was conjectured in Borodin et al. [J. Comput. System Sci., 22 (1981), pp. 351--364] that to solve the element distinctness problem requires $TS = \Omega(n^2)$ on a comparison-based branching program using space $S$ and time $T$, which, if true, would ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 50, Issue 2

March 2003

169 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/636865

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2003

Published in JACM Volume 50, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
910
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hamoudi YMagniez F(2023)Quantum Time–Space Tradeoff for Finding Multiple Collision PairsACM Transactions on Computation Theory10.1145/358998615:1-2(1-22)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3589986
Cook SMcKenzie PWehr DBraverman MSanthanam R(2023)Pebbles and Branching Programs for Tree EvaluationLogic, Automata, and Computational Complexity10.1145/3588287.3588303(261-318)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588287.3588303
Williams R(2022)Some Estimated Likelihoods for Computational ComplexityComputing and Software Science10.1007/978-3-319-91908-9_2(9-26)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-91908-9_2
Dinur I(2020)Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their ApplicationsAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45721-1_15(405-434)Online publication date: 10-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45721-1_15
Hoza WAceto L(2019)Typically-correct derandomization for small time and spaceProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.9(1-39)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.9
McKay DMurray CWilliams RCharikar MCohen E(2019)Weak lower bounds on resource-bounded compression imply strong separations of complexity classesProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316396(1215-1225)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316396
Edmonds JMedabalimi VPitassi TServedio R(2018)Hardness of function composition for semantic read once branching programsProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235601(1-22)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235601
Raz R(2018)Fast Learning Requires Good MemoryJournal of the ACM10.1145/318656366:1(1-18)Online publication date: 12-Dec-2018
https://dl.acm.org/doi/10.1145/3186563
Anderson MForbes MSaptharishi RShpilka AVolk B(2018)Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching ProgramsACM Transactions on Computation Theory10.1145/317070910:1(1-30)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3170709
Carboni Oliveira ISanthanam R(2018)Hardness Magnification for Natural Problems2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00016(65-76)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00016
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents