Document Open Access Logo

Derandomizing Isolation in Space-Bounded Settings

Authors Dieter van Melkebeek, Gautam Prakriya

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.5.pdf
  • Filesize: 0.74 MB
  • 32 pages

Document Identifiers

Author Details

Dieter van Melkebeek
Gautam Prakriya

Cite As Get BibTex

Dieter van Melkebeek and Gautam Prakriya. Derandomizing Isolation in Space-Bounded Settings. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.5

Abstract

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance on shallow semi-unbounded circuits.

A common approach employs small weight assignments that make the solution of minimum weight unique. The Isolation Lemma and other known procedures use Omega(n) random bits to generate weights of individual bitlength O(log(n)). We develop a derandomized version for both settings that uses O(log(n)^{3/2}) random bits and produces weights of bitlength O(log(n)^{3/2}) in logarithmic space. The construction allows us to show that every language in NL can be accepted by a nondeterministic machine that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input. Similarly, every language in LogCFL can be accepted by a nondeterministic machine equipped with a stack that does not count towards the space bound, that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input.  

We also show that the existence of somewhat more restricted isolations for reachability on digraphs implies that NL can be decided in logspace with polynomial advice. A similar result holds for certifying acceptance on shallow semi-unbounded circuits and LogCFL.

Subject Classification

Keywords
  • Isolation lemma
  • derandomization
  • unambiguous nondeterminism
  • graph reachability
  • circuit certification

Metrics

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

References

  1. A. Aggarwal, R. J. Anderson, and M.-Y. Kao. Parallel depth-first search in general directed graphs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 297-308, 1989. URL: http://dx.doi.org/10.1145/73007.73035.
  2. M. Agrawal, R. Gurjar, A. Korwar, and N. Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669-697, 2015. URL: http://dx.doi.org/10.1137/140975103.
  3. E. Allender and U. Hertrampf. Depth reduction for circuits of unbounded fan-in. Information and Computation, 112(2):217-238, 1994. Google Scholar
  4. E. Allender, K. Reinhardt, and S. Zhou. Isolation, matching, and counting uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59(2):164-181, 1999. URL: http://dx.doi.org/10.1006/jcss.1999.1646.
  5. R. Arora, A. Gupta, R. Gurjar, and R. Tewari. Derandomizing Isolation Lemma for K_3,3-free and K₅-free Bipartite Graphs. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, pages 10:1-10:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.10.
  6. V. Arvind and P. Mukhopadhyay. Derandomizing the isolation lemma and lower bounds for circuit size. In Proceedings of the 12th Intl. Workshop on Randomization and Computation, pages 276-289, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85363-3_23.
  7. V. Arvind, P. Mukhopadhyay, and S. Srinivasan. New results on noncommutative and commutative polynomial identity testing. Computational Complexity, 19(4):521-558, 2010. URL: http://dx.doi.org/10.1007/s00037-010-0299-8.
  8. G. Barnes, J. F. Buss, W. L. Ruzzo, and B. Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM Journal on Computing, 27(5):1273-1282, 1998. Google Scholar
  9. R. Beigel, N. Reingold, and D. Spielman. The perceptron strikes back. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 286-291, 1991. URL: http://dx.doi.org/10.1109/SCT.1991.160270.
  10. S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44(2):193-219, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90019-F.
  11. A. Björklund. Determinant sums for undirected hamiltonicity. SIAM Journal on Computing, 43(1):280-299, 2014. URL: http://dx.doi.org/10.1137/110839229.
  12. A. Björklund and T. Husfeldt. Shortest two disjoint paths in polynomial time. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, pages 211-222, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_18.
  13. C. Bourke, R. Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory, 1(1), 2009. URL: http://dx.doi.org/10.1145/1490270.1490274.
  14. T. Brunsch, K. Cornelissen, B. Manthey, and H. Röglin. Smoothed analysis of belief propagation for minimum-cost flow and matching. In Proceedings of the 7th International Workshop on Algorithms and Computation, pages 182-193, 2013. URL: http://dx.doi.org/10.1007/978-3-642-36065-7_18.
  15. J.-Y. Cai, V. T. Chakaravarthy, and D. van Melkebeek. Time-space tradeoff in derandomizing probabilistic logspace. Theory Comput. Syst., 39(1):189-208, 2006. URL: http://dx.doi.org/10.1007/s00224-005-1264-9.
  16. C. Calabro, R. Impagliazzo, V. Kabanets, and R. Paturi. The complexity of unique k-SAT: an isolation lemma for k-CNFs. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pages 135-141, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214416.
  17. J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. URL: http://dx.doi.org/10.1016/0022-0000(79)90044-8.
  18. S. Chari, P. Rohatgi, and A. Srinivasan. Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM Journal on Computing, 24(5):1036-1050, 1995. URL: http://dx.doi.org/10.1137/S0097539793250330.
  19. M. Cygan, S. Kratsch, and J. Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 301-310, 2013. URL: http://dx.doi.org/10.1145/2488608.2488646.
  20. M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 150-159, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  21. S. I. Daitch and D. A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 451-460, 2008. URL: http://dx.doi.org/10.1145/1374376.1374441.
  22. S. Datta, W. Hesse, and R. Kulkarni. Dynamic complexity of directed reachability and other problems. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, pages 356-367, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_30.
  23. S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume. Reachability is in DynFO. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 159-170, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_13.
  24. S. Datta, R. Kulkarni, and S. Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory Comput. Syst., 47(3):737-757, 2010. URL: http://dx.doi.org/10.1007/s00224-009-9204-8.
  25. S. Datta, R. Kulkarni, R. Tewari, and N. V. Vinodchandran. Space complexity of perfect matching in bounded genus bipartite graphs. Journal of Computer and System Sciences, 78(3):765-779, 2012. Google Scholar
  26. H. Dell, V. Kabanets, D. van Melkebeek, and O. Watanabe. Is Valiant-Vazirani’s isolation probability improvable? Computational Complexity, 22(2):345-383, 2013. URL: http://dx.doi.org/10.1007/s00037-013-0059-7.
  27. J. Erickson and P. Worah. Computing the shortest essential cycle. Discrete and Computational Geometry, 44(4):912-930, 2010. URL: http://dx.doi.org/10.1007/s00454-010-9241-8.
  28. S. A. Fenner, R. Gurjar, and T. Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 754-763, 2016. URL: http://dx.doi.org/10.1145/2897518.2897564.
  29. F. V. Fomin and P. Kaski. Exact exponential algorithms. Communications of the ACM, 56(3):80-88, March 2013. URL: http://dx.doi.org/10.1145/2428556.2428575.
  30. A. Gál and A. Wigderson. Boolean complexity classes vs. their arithmetic analogs. Random Struct. Algorithms, 9(1-2):99-111, 1996. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199608/09)9:1/2<99::AID-RSA7>3.0.CO;2-6.
  31. D. Gamarnik, D. Shah, and Y. Wei. Belief propagation for min-cost network flow: Convergence and correctness. Operations Research, 60(2):410-428, 2012. URL: http://dx.doi.org/10.1287/opre.1110.1025.
  32. I. Haviv and O. Regev. On the lattice isomorphism problem. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 391-404, 2014. URL: http://dl.acm.org/citation.cfm?id=2634074.2634103.
  33. H. Hirai and H. Namba. Shortest (A+B)-path packing via hafnian. Computing Research Repository, abs/1603.08073, 2016. URL: http://arxiv.org/abs/1603.08073.
  34. V. A. T. Kallampally and R. Tewari. Trading Determinism for Time in Space Bounded Computations. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, pages 10:1-10:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.10.
  35. R. Kannan, H. Venkateswaran, V. Vinay, and A.C. Yao. A circuit-based proof of Toda’s theorem. Information and Computing, 104(2):271-276, 1993. Google Scholar
  36. Y. Kanoria, M. Bayati, C. Borgs, J. Chayes, and A. Montanari. Fast convergence of natural bargaining dynamics in exchange networks. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1518-1537, 2011. URL: http://dl.acm.org/citation.cfm?id=2133036.2133154.
  37. R. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random nc. Combinatorica, 6(1):35-48, 1986. URL: http://dx.doi.org/10.1007/BF02579407.
  38. S. Kiefer, A. S. Murawski, J. Ouaknine, B. Wachter, and J. Worrell. On the complexity of equivalence and minimisation for Q-weighted automata. Logical Methods in Computer Science, 9(1), 2013. URL: http://dx.doi.org/10.2168/LMCS-9(1:8)2013.
  39. A. Klivans and D. A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 216-223, 2001. URL: http://dx.doi.org/10.1145/380752.380801.
  40. A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. URL: http://dx.doi.org/10.1137/S0097539700389652.
  41. K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26(2):209-211, 1983. Google Scholar
  42. V. Krishan and N. Limaye. Isolation lemma for directed reachability and NL vs. L. Electronic Colloquium on Computational Complexity, 23:155, 2016. URL: http://eccc.hpi-web.de/report/2016/155.
  43. J. Kynčl and T. Vyskočil. Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM Transactions on Computation Theory, 1(3):8:1-8:11, March 2010. URL: http://dx.doi.org/10.1145/1714450.1714451.
  44. A. Lingas and M. Karpinski. Subtree isomorphism is NC reducible to bipartite perfect matching. Information Processing Letters, 30(1):27-32, 1989. URL: http://dx.doi.org/10.1016/0020-0190(89)90170-1.
  45. A. Lingas and M. Persson. A fast parallel algorithm for minimum-cost small integral flows. Algorithmica, 72(2):607-619, 2015. URL: http://dx.doi.org/10.1007/s00453-013-9865-1.
  46. R. Majumdar and J. L. Wong. Watermarking of SAT using combinatorial isolation lemmas. In Proceedings of the 38th Annual Design Automation Conference, pages 480-485, 2001. URL: http://dx.doi.org/10.1145/378239.378566.
  47. K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 345-354, 1987. URL: http://dx.doi.org/10.1145/28395.383347.
  48. N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: http://dx.doi.org/10.1007/BF01305237.
  49. N. Nisan. RL subseteq SC. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 619-623, 1992. URL: http://dx.doi.org/10.1145/129712.129772.
  50. J. B. Orlin and C. Stein. Parallel algorithms for the assignment and minimum-cost flow problems. Operations research letters, 14(4):181-186, 1993. Google Scholar
  51. K. Reinhardt and E. Allender. Making nondeterminism unambiguous. SIAM Journal on Computing, 29(4):1118-1131, 2000. URL: http://dx.doi.org/10.1137/S0097539798339041.
  52. M. E. Saks and S. Zhou. BP_HSPACE(S) ⊆ DSPACE(S^3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. URL: http://dx.doi.org/10.1006/jcss.1998.1616.
  53. W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. URL: http://dx.doi.org/10.1016/S0022-0000(70)80006-X.
  54. Y. Strozecki. On enumerating monomials and other combinatorial structures by polynomial interpolation. Theory of Computing Systems, 53(4):532-568, 2013. URL: http://dx.doi.org/10.1007/s00224-012-9442-z.
  55. I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the ACM, 25(3):405-414, July 1978. URL: http://dx.doi.org/10.1145/322077.322083.
  56. J. Tarui. Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy. Theoretical Computer Science, 113(1):167-183, 1993. Google Scholar
  57. T. Thierauf and F. Wagner. Reachability in K_3,3-free and K₅-free graphs is in unambiguous logspace. Chicago Journal of Theoretical Computer Science, 2015, 2015. URL: http://cjtcs.cs.uchicago.edu/articles/2015/2/contents.html.
  58. S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  59. P. Traxler. The time complexity of constraint satisfaction. In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, pages 190-201, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79723-4_18.
  60. L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(3):85-93, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90135-0.
  61. H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43(2):380-404, October 1991. URL: http://dx.doi.org/10.1016/0022-0000(91)90020-6.
  62. H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, 1999. Google Scholar
  63. O. Watanabe and S. Toda. Structural analysis of the complexity of inverse functions. Mathematical Systems Theory, 26(2):203-214, 1993. 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