Document Open Access Logo

A Unified Method for Placing Problems in Polylogarithmic Depth

Authors Andreas Krebs, Nutan Limaye, Michael Ludwig

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.36.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Andreas Krebs
Nutan Limaye
Michael Ludwig

Cite AsGet BibTex

Andreas Krebs, Nutan Limaye, and Michael Ludwig. A Unified Method for Placing Problems in Polylogarithmic Depth. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2017.36

Abstract

In this work we consider the term evaluation problem which is, given a term over some algebra and a valid input to the term, computing the value of the term on that input. In contrast to previous methods we allow the algebra to be completely general and consider the problem of obtaining an efficient upper bound for this problem. Many variants of the problems where the algebra is well behaved have been studied. For example, the problem over the Boolean semiring or over the semiring (N,+,*). We extend this line of work. Our efficient term evaluation algorithm then serves as a tool for obtaining polylogarithmic depth upper bounds for various well-studied problems. To demonstrate the utility of our result we show new bounds and reprove known results for a large spectrum of problems. In particular, the applications of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word problems for tree and visibly pushdown automata, and various problems related to bounded tree-width and clique-width graphs.
Keywords
  • Polylogarithmic depth
  • Term evaluation
  • Parallel algorithms

Metrics

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

References

  1. Manindra Agrawal, Thanh Minh Hoang, and Thomas Thierauf. The polynomially bounded perfect matching problem is in nc^2. In STACS, volume 4393, pages 489-499, 2007. Google Scholar
  2. Eric Allender and Ian Mertz. Complexity of regular functions. In Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, volume 8977 of Lecture Notes in Computer Science, pages 449-460. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15579-1_35.
  3. Nikhil Balaji, Samir Datta, and Venkatesh Ganesan. Counting euler tours in undirected bounded treewidth graphs. In Prahladh Harsha and G. Ramalingam, editors, 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, volume 45 of LIPIcs, pages 246-260. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.246.
  4. Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201-206, 1974. URL: http://dx.doi.org/10.1145/321812.321815.
  5. Samuel R. Buss. The boolean formula value problem is in ALOGTIME. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 123-131. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28409.
  6. Samuel R. Buss. Algorithms for boolean formula evaluation and for tree contraction. In Arithmetic, Proof Theory and Computational Complexity, pages 96-115. Oxford University Press, 1993. Google Scholar
  7. Samuel R. Buss, Stephen A. Cook, A. Gupta, and V. Ramachandran. An optimal parallel algorithm for formula evaluation. SIAM J. Comput., 21(4):755-780, 1992. URL: http://dx.doi.org/10.1137/0221046.
  8. Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1-3):2-21, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80041-3.
  9. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  10. Patrick W. Dymond. Input-driven languages are in log n depth. Inf. Process. Lett., 26(5):247-250, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90148-2.
  11. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 143-152. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  12. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Guest column: Parallel algorithms for perfect matching. SIGACT News, 48(1):102-109, 2017. URL: http://dx.doi.org/10.1145/3061640.3061655.
  13. Merrick Furst, James B Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Theory of Computing Systems, 17(1):13-27, 1984. Google Scholar
  14. Moses Ganardi and Markus Lohrey. A universal tree balancing theorem. CoRR, abs/1704.08705, 2017. URL: http://arxiv.org/abs/1704.08705.
  15. A. Gupta. A fast parallel algorithm for recognition of parenthesis languages. Master’s thesis, University of Toronto, 1985. Google Scholar
  16. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. URL: http://dx.doi.org/10.1137/140957123.
  17. Johan Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 6-20. ACM, 1986. Google Scholar
  18. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699-1708, 2014. URL: http://dx.doi.org/10.1137/120897432.
  19. Joseph JáJá. An introduction to parallel algorithms, volume 17. Addison-Wesley Reading, 1992. Google Scholar
  20. Maurice J. Jansen and Jayalal Sarma. Balancing bounded treewidth circuits. Theory Comput. Syst., 54(2):318-336, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9519-3.
  21. Andreas Krebs, Nutan Limaye, and Michael Ludwig. Cost register automata for nested words. In Thang N. Dinh and My T. Thai, editors, Computing and Combinatorics - 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings, volume 9797 of Lecture Notes in Computer Science, pages 587-598. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-42634-1_47.
  22. Andreas Krebs, Nutan Limaye, and Michael Ludwig. A unified method for placing problems in polylogarithmic depth. Electronic Colloquium on Computational Complexity (ECCC), 24:19, 2017. URL: https://eccc.weizmann.ac.il/report/2017/019.
  23. Andreas Krebs, Nutan Limaye, and Meena Mahajan. Counting paths in VPA is complete for #NC^1. In My T. Thai and Sartaj Sahni, editors, Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings, volume 6196 of Lecture Notes in Computer Science, pages 44-53. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14031-0_7.
  24. Andreas Krebs, Nutan Limaye, and Meena Mahajan. Counting paths in VPA is complete for #nc 1. Algorithmica, 64(2):279-294, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9501-x.
  25. Vipin Kumar, Ananth Grama, Anshul Gupta, and George Karypis. Introduction to parallel computing: design and analysis of algorithms, volume 400. Benjamin/Cummings Redwood City, 1994. Google Scholar
  26. Markus Lohrey. On the parallel complexity of tree automata. In Aart Middeldorp, editor, Rewriting Techniques and Applications, 12th International Conference, RTA 2001, Utrecht, The Netherlands, May 22-24, 2001, Proceedings, volume 2051 of Lecture Notes in Computer Science, pages 201-215. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-45127-7_16.
  27. Nancy A. Lynch. Log space recognition and translation of parenthesis languages. J. ACM, 24(4):583-590, 1977. URL: http://dx.doi.org/10.1145/322033.322037.
  28. Meena Mahajan and V. Vinay. A combinatorial algorithm for the determinant. In Michael E. Saks, editor, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana., pages 730-738. ACM/SIAM, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314429.
  29. Kurt Mehlhorn. Pebbling moutain ranges and its application of dcfl-recognition. In J. W. de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherland, July 14-18, 1980, Proceedings, volume 85 of Lecture Notes in Computer Science, pages 422-435. Springer, 1980. URL: http://dx.doi.org/10.1007/3-540-10003-2_89.
  30. Dan I Moldovan. Parallel processing from applications to systems. Elsevier, 2014. Google Scholar
  31. V. Ramachandran. Restructuring formula trees. Unpublished manuscript, 1986. Google Scholar
  32. Walter L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22(3):365-383, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90038-6.
  33. P.M. Spira. On time hardware complexity tradeoffs for boolean functions. Proceedings of the Fourth Hawaii International Symposium on System Sciences, pages 525-527, 1971. Google Scholar
  34. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, 1994. Google Scholar
  35. Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. URL: http://dx.doi.org/10.1007/978-3-662-03927-4.
  36. Heribert Vollmer. Introduction to circuit complexity: a uniform approach, 2013. Google Scholar
  37. Egon Wanke. k-nlc graphs and polynomial algorithms. Discrete Applied Mathematics, 54(2-3):251-266, 1994. URL: http://dx.doi.org/10.1016/0166-218X(94)90026-4.
  38. Barry Wilkinson and Michael Allen. Parallel programming: techniques and applications using networked workstations and parallel computers. Prentice-Hall, 1999. 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 Imprint Privacy Contact