Document Open Access Logo

Karchmer-Wigderson Games for Hazard-Free Computation

Authors Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.74.pdf
  • Filesize: 0.78 MB
  • 25 pages

Document Identifiers

Author Details

Christian Ikenmeyer
  • University of Warwick, Coventry, UK
Balagopal Komarath
  • IIT Gandhinagar, India
Nitin Saurabh
  • IIT Hyderabad, India

Funding

  • Saurabh, Nitin: This project has received funding from the the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.

Acknowledgements

We thank Igor Sergeev for his support with the literature. Nitin Saurabh would like to thank Yuval Filmus for helpful discussions. We would also like to thank anonymous reviewers for useful suggestions that greatly improved the presentation.

Cite AsGet BibTex

Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh. Karchmer-Wigderson Games for Hazard-Free Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 74:1-74:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.74

Abstract

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth 2 that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Communication complexity
  • Theory of computation → Concurrency
  • Hardware → Combinational circuits
Keywords
  • Hazard-free computation
  • monotone computation
  • Karchmer-Wigderson games
  • communication complexity
  • lower bounds

Metrics

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

Related Versions

References

  1. N. Alon and R. B. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1-22, January 1987. URL: https://doi.org/10.1007/BF02579196.
  2. A. E. Andreev. On one method of obtaining constructive lower bounds for the monotone circuit size. Algebra and Logics, 26(1):3-26, 1987. Google Scholar
  3. R. Beals, T. Nishino, and K. Tanaka. On the complexity of negation-limited boolean networks. SIAM Journal on Computing, 27(5):1334-1347, 1998. Google Scholar
  4. A. Becker, W. Hu, Y. Tai, P. Brisk, R. Kastner, and P. Ienne. Arbitrary precision and complexity tradeoffs for gate-level information flow tracking. In 2017 54th ACM/EDAC/IEEE Design Automation Conference (DAC), pages 1-6, 2017. URL: https://doi.org/10.1145/3061639.3062203.
  5. J. Brzozowski, Z. Esik, and Y. Iland. Algebras for hazard detection. In Proc. 31st International Symposium on Multiple-Valued Logic, 2001. Google Scholar
  6. J. A. Brzozowski and C-J. H. Seger. Asynchronous circuits. Springer New York, 1995. Google Scholar
  7. J. Bund, C. Lenzen, and M. Medina. Near-optimal metastability-containing sorting networks. In Design, Automation Test in Europe Conference Exhibition (DATE), 2017, pages 226-231, 2017. URL: https://doi.org/10.23919/DATE.2017.7926987.
  8. J. Bund, C. Lenzen, and M. Medina. Optimal metastability-containing sorting networks. In 2018 Design, Automation Test in Europe Conference Exhibition (DATE), pages 521-526, 2018. URL: https://doi.org/10.23919/DATE.2018.8342063.
  9. J. Bund, C. Lenzen, and M. Medina. Optimal metastability-containing sorting via parallel prefix computation. IEEE Transactions on Computers, 69(2):198-211, 2020. URL: https://doi.org/10.1109/TC.2019.2939818.
  10. S. H. Caldwell. Switching Circuits and Logical Design. John Wiley & Sons Inc, 1958. Google Scholar
  11. A. K. Chandra and G. Markowsky. On the number of prime implicants. Discrete Mathematics, 24(1):7-11, 1978. Google Scholar
  12. J. Edmonds, R. Impagliazzo, S. Rudich, and J. Sgall. Communication complexity towards lower bounds on circuit depth. Comput. Complex., 10(3):210-246, 2001. URL: https://doi.org/10.1007/s00037-001-8195-x.
  13. E. B. Eichelberger. Hazard detection in combinational and sequential switching circuits. IBM J. Res. Dev., 9(2):90-99, March 1965. URL: https://doi.org/10.1147/rd.92.0090.
  14. Y. Filmus, O. Meir, and A. Tal. Shrinkage under random projections, and cubic formula lower bounds for AC0 (extended abstract). In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPIcs, pages 89:1-89:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.89.
  15. M. J. Fischer. The complexity of negation-limited networks—a brief survey. In Automata Theory and Formal Languages, pages 71-82. Springer, 1975. Google Scholar
  16. S. Friedrichs, M. Függer, and C. Lenzen. Metastability-containing circuits. IEEE Transactions on Computers, 67(08):1167-1183, August 2018. URL: https://doi.org/10.1109/TC.2018.2808185.
  17. M. Függer, A. Kinali, C. Lenzen, and T. Polzer. Metastability-aware memory-efficient time-to-digital converters. In 2017 23rd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 49-56, 2017. URL: https://doi.org/10.1109/ASYNC.2017.12.
  18. A. Gál. A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity, 10(4):277-296, 2001. URL: https://doi.org/10.1007/s000370100001.
  19. M. Göös and T. Pitassi. Communication lower bounds via critical block sensitivity. In Symposium on Theory of Computing, STOC 2014, pages 847-856. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591838.
  20. M. Goto. Application of logical mathematics to the theory of relay networks (in Japanese). J. Inst. Elec. Eng. of Japan, 64(726):125-130, 1949. Google Scholar
  21. M. Grigni and M. Sipser. Monotone separation of logarithmic space from logarithmic depth. Journal of Computer and System Sciences, 50(3):433-437, 1995. Google Scholar
  22. M. Grzegorz. Kleene logic and inference. Bulletin of the Section of Logic, 43(1/2):42-52, 2014. Google Scholar
  23. D. Harnik and R. Raz. Higher lower bounds on monotone size. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 378-387. ACM, 2000. URL: https://doi.org/10.1145/335305.335349.
  24. J. Håstad. The shrinkage exponent of de morgan formulas is 2. SIAM Journal on Computing, 27(1):48-64, 1998. URL: https://doi.org/10.1137/S0097539794261556.
  25. W. Hu, J. Oberg, A. Irturk, M. Tiwari, T. Sherwood, D. Mu, and R. Kastner. On the complexity of generating gate level information flow tracking logic. IEEE Transactions on Information Forensics and Security, 7(3):1067-1080, June 2012. URL: https://doi.org/10.1109/TIFS.2012.2189105.
  26. D. A. Huffman. The design and use of hazard-free switching networks. J. ACM, 4(1):47-62, January 1957. URL: https://doi.org/10.1145/320856.320866.
  27. C. Ikenmeyer, B. Komarath, C. Lenzen, V. Lysikov, A. Mokhov, and K. Sreenivasaiah. On the complexity of hazard-free circuits. J. ACM, 66(4), 2019. URL: https://doi.org/10.1145/3320123.
  28. S. Jukna. Notes on hazard-free circuits. SIAM Journal on Discrete Mathematics, 35(2):770-787, 2021. URL: https://doi.org/10.1137/20M1355240.
  29. M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255-265, 1990. URL: https://doi.org/10.1137/0403021.
  30. V. M. Khrapchenko. Complexity of the realization of a linear function in the class of Π-circuits. Mathematical Notes of the Academy of Sciences of the USSR, 9(1):21-23, 1971. Google Scholar
  31. S. C. Kleene. On notation for ordinal numbers. The Journal of Symbolic Logic, 3(4):150-155, 1938. URL: http://www.jstor.org/stable/2267778.
  32. S. C. Kleene. Introduction to Metamathematics. North Holland, 1952. Google Scholar
  33. S. Körner. Experience and theory : an essay in the philosophy of science. International library of philosophy and scientific method. Routledge & Kegan Paul, London, 1966. Google Scholar
  34. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1996. URL: https://doi.org/10.1017/CBO9780511574948.
  35. C. Lenzen and M. Medina. Efficient metastability-containing gray code 2-sort. In 2016 22nd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 49-56, 2016. URL: https://doi.org/10.1109/ASYNC.2016.18.
  36. S. Lozhkin. Tighter bounds on the complexity of control systems from some classes. Mat. Voprosy Kibernetiki, 6:189-214, 1996. in Russian. Google Scholar
  37. S. Lozhkin and N. Vlasov. On multiplexer function complexity in the π-schemes class. Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 151(2):98-106, 2009. in Russian. URL: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=uzku&paperid=750&option_lang=eng.
  38. S. Lozhkin and N. Vlasov. On the depth of the storage access function. Moscow University Computational Mathematics and Cybernetics, 35(2):97-104, 2011. Google Scholar
  39. O. B. Lupanov. On a method of circuit synthesis. Izvestia VUZ, 1:120-140, 1958. Google Scholar
  40. O. B. Lupanov. On the complexity of realization of functions of propositional calculus by formulas. Problemy Kibernetiki, 3:61-80, 1960. in Russian. Google Scholar
  41. O. B. Lupanov. On the synthesis of some classes of control systems. Problemy Kibernetiki, 10:63-97, 1963. in Russian. Google Scholar
  42. K. Mehlhorn and E. M. Schmidt. Las vegas is better than determinism in VLSI and distributed computing. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 330-337, 1982. Google Scholar
  43. O. Meir. Toward better depth lower bounds: Two results on the multiplexor relation. Comput. Complex., 29(1):4, 2020. URL: https://doi.org/10.1007/s00037-020-00194-8.
  44. M. Mendler, T. R. Shiple, and G. Berry. Constructive boolean circuits and the exactness of timed ternary simulation. Formal Methods in System Design, 40:283-329, 2012. URL: https://doi.org/10.1007/s10703-012-0144-6.
  45. M. Mukaidono. On the b-ternary logical function - a ternary logic considering ambiguity. Systems, Computers, Controls, 3(3):27-36, 1972. Google Scholar
  46. M. Mukaidono. Advanced results on application of fuzzy switching functions to hazard detection. In P.P. Wong, editor, Advances in Fuzzy Sets, Possibility Theory and Applications, pages 335-349. Plenum Publishing Corporation, 1983. Google Scholar
  47. M. Mukaidono. Regular ternary logic functions - ternary logic functions suitable for treating ambiguity. In Proc. 13th International Symposium on Multiple-Valued Logic, pages 286-291. IEEE Computer Society Press, 1983. Google Scholar
  48. S. M. Nowick and D. L. Dill. Exact two-level minimization of hazard-free logic with multiple-input changes. In 1992 IEEE/ACM International Conference on Computer-Aided Design, pages 626-630, November 1992. URL: https://doi.org/10.1109/ICCAD.1992.279301.
  49. T. Pitassi and R. Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1246-1255. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055478.
  50. T. Pitassi and R. Robere. Lifting nullstellensatz to monotone span programs over any field. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1207-1219. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188914.
  51. P. Pudlák. On extracting computations from propositional proofs (a survey). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, volume 8 of LIPIcs, pages 30-41. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.30.
  52. A. Rao and A. Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108671644.
  53. R. Raz and P. McKenzie. Separation of the monotone NC hierarchy. Comb., 19(3):403-435, 1999. URL: https://doi.org/10.1007/s004930050062.
  54. R. Raz and A. Wigderson. Monotone circuits for matching require linear depth. Journal of the ACM (JACM), 39(3):736-744, 1992. Google Scholar
  55. A. A. Razborov. Lower bounds for the monotone complexity of some boolean functions. In Soviet Math. Dokl., volume 31, pages 354-357, 1985. Google Scholar
  56. A. A. Razborov. Lower bounds on monotone complexity of the logical permanent. Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485-493, 1985. Google Scholar
  57. A. A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  58. A. A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: Mathematics, 59(1):205-227, 1995. URL: https://doi.org/10.1070/im1995v059n01abeh000009.
  59. J. Riordan and C. E. Shannon. The number of two-terminal series-parallel networks. Journal of Mathematics and Physics, 21(1-4):83-93, 1942. Google Scholar
  60. C. E. Shannon. The synthesis of two-terminal switching circuits. The Bell System Technical Journal, 28(1):59-98, 1949. Google Scholar
  61. D. Sokolov. Dag-like communication and its applications. In International Computer Science Symposium in Russia, pages 294-307. Springer, 2017. Google Scholar
  62. K. Tanaka, T. Nishino, and R. Beals. Negation-limited circuit complexity of symmetric functions. Information processing letters, 59(5):273-279, 1996. Google Scholar
  63. G. Tarawneh, M. Függer, and C. Lenzen. Metastability tolerant computing. In 2017 23rd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 25-32, 2017. URL: https://doi.org/10.1109/ASYNC.2017.9.
  64. E. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141-142, 1988. Google Scholar
  65. G. Tardos and U. Zwick. The communication complexity of the universal relation. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, 1997, pages 247-259. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/CCC.1997.612320.
  66. M. Tiwari, H. M. G. Wassel, B. Mazloom, S. Mysore, F. T. Chong, and T. Sherwood. Complete information flow tracking from the gates up. SIGARCH Comput. Archit. News, 37(1):109-120, March 2009. URL: https://doi.org/10.1145/2528521.1508258.
  67. M. Yoeli and S. Rinon. Application of ternary algebra to the study of static hazards. J. ACM, 11(1):84-97, January 1964. URL: https://doi.org/10.1145/321203.321214.
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