Document Open Access Logo

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs

Authors Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.36.pdf
  • Filesize: 474 kB
  • 13 pages

Document Identifiers

Author Details

Stephen Cook
Jeff Edmonds
Venkatesh Medabalimi
Toniann Pitassi

Cite As Get BibTex

Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, and Toniann Pitassi. Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.36

Abstract

We prove exponential lower bounds on the size of semantic read-once 3-ary nondeterministic branching programs. Prior to our result the best that was known was for D-ary branching programs with |D| >= 2^{13}.

Subject Classification

Keywords
  • Branching Programs
  • Semantic
  • Non-deterministic
  • Lower Bounds

Metrics

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

References

  1. M. Ajtai. A non-linear time lower bound for boolean branching programs. In Proceedings 40th FOCS, pages 60-70, 1999. Google Scholar
  2. P. Beame, T.S. Jayram, and M. Saks. Time-space tradeoffs for branching programs. J. Comput. Syst. Sci, 63(4):542-572, 2001. Google Scholar
  3. P. Beame, M. Saks, X. Sun, and E. Vee. Time-space trade-off lower bounds for randomized computation of decision problems. Journal of the ACM, 50(2):154-195, 2003. Google Scholar
  4. Allan Borodin, A Razborov, and Roman Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3(1):1-18, 1993. Google Scholar
  5. Alan Cobham. The recognition problem for the set of perfect squares. In Switching and Automata Theory, 1966., IEEE Conference Record of Seventh Annual Symposium on, pages 78-87. IEEE, 1966. Google Scholar
  6. Scott Diehl and Dieter Van Melkebeek. Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM Journal on Computing, 36(3):563-594, 2006. Google Scholar
  7. L. Fortnow. Nondeterministic polynomial time versus nondeterministic logarithmic space: Time space tradeoffs for satifiability. In Proceedings 12th Conference on Computational Complexity, pages 52-60, 1997. Google Scholar
  8. L. Fortnow and D. Van Melkebeek. Time-space tradeoffs for nondeterministic computation. In Proceedings 15th Conference on Computational Complexity, pages 2-13, 2000. Google Scholar
  9. Lance Fortnow, Richard Lipton, Dieter Van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. Journal of the ACM (JACM), 52(6):835-865, 2005. Google Scholar
  10. S. Jukna. A nondeterministic space-time tradeoff for linear codes. Information Processing Letters, 109(5):286-289, 2009. Google Scholar
  11. Stasys Jukna. A note on read-k times branching programs. Informatique théorique et applications, 29(1):75-83, 1995. Google Scholar
  12. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science &Business Media, 2012. Google Scholar
  13. Stasys P Jukna. The effect of null-chains on the complexity of contact schemes. In Fundamentals of Computation Theory, pages 246-256. Springer, 1989. Google Scholar
  14. Matthias Krause, Christoph Meinel, and Stephan Waack. Separating the eraser turing machine classes le, nle, co-nle and pe. In Mathematical Foundations of Computer Science 1988, pages 405-413. Springer, 1988. Google Scholar
  15. R. Lipton and A. Viglas. Time-space tradeoffs for sat. In Proceedings 40th FOCS, pages 459-464, 1999. Google Scholar
  16. EA Okolnishnikova. On lower bounds for branching programs. Siberian Advances in Mathematics, 3(1):152-166, 1993. Google Scholar
  17. Pavel Pudlak and Stanislav Zak. Space complexity of computations. Preprint Univ. of Prague, 1983. Google Scholar
  18. Ryan Williams. Better time-space lower bounds for sat and related problems. In Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on, pages 40-49. IEEE, 2005. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact