Characterization and Lower Bounds for Branching Program Size Using Projective Dimension

Authors Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.37.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Krishnamoorthy Dinesh
Sajin Koroth
Jayalal Sarma

Cite AsGet BibTex

Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma. Characterization and Lower Bounds for Branching Program Size Using Projective Dimension. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.37

Abstract

We study projective dimension, a graph parameter (denoted by pd(G) for a graph G), introduced by Pudlak and Rodl (1992). For a Boolean function f(on n bits), Pudlak and Rodl associated a bipartite graph G_f and showed that size of the optimal branching program computing f (denoted by bpsize(f)) is at least pd(G_f) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) imply lower bounds for bpsize(f). Despite several attempts (Pudlak and Rodl (1992), Ronyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f) is 2^{Omega(n)}. Motivated by the argument in Pudlak and Rodl (1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd(f)) and {bitwise decomposable projective dimension} (denoted by bpdim(f)). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2^{Omega(n)}. In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a large constant c>0 and for any function f, bpdim(f)/6 <= bpsize(f) <= (bpdim(f))^c. (b) We introduce a new candidate function family f for showing super-polynomial lower bounds for bpdim(f). As our main result, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(sqrt{n}), upd(f) = Omega(n), bpdim(f) = Omega({n^{1.5}}/{log(n)}). (c) Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.
Keywords
  • Projective Dimension
  • Lower Bounds
  • Branching Program Size

Metrics

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

References

  1. Paul Beame, Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Nondeterminism and an abstract formulation of Nečiporuk’s lower bound method. CoRR, abs/1608.01932, 2016. URL: http://arxiv.org/abs/1608.01932.
  2. Béla Bollobás. Random Graphs, Second edition. Cambridge Studies in Advanced Mathematics 73. Cambridge University Press, 2001. Google Scholar
  3. Philippe Delsarte. Association schemes and t-designs in regular semilattices. Journal of Combinatorial Theory, Series A, 20(2):230-243, mar 1976. URL: http://dx.doi.org/10.1016/0097-3165(76)90017-0.
  4. Péter Frankl and Ronald L. Graham. Intersection theorems for vector spaces. European Journal of Combinatorics, 6(2):183-187, jun 1985. URL: http://dx.doi.org/10.1016/s0195-6698(85)80009-3.
  5. Péter Frankl and Richard M. Wilson. The Erdős-Ko-Rado theorem for vector spaces. Journal of Combinatorial Theory Series A, 43(2):228-236, nov 1986. URL: http://dx.doi.org/10.1016/0097-3165(86)90063-4.
  6. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27 of Series: Algorithms and Combinatorics. Springer New York Inc., 2012. Google Scholar
  7. Dinesh Krishnamoorthy, Sajin Koroth, and Jayalal Sarma. Characterization and lower bounds for branching program size using projective dimension. CoRR, abs/1604.07200, 2016. URL: http://arxiv.org/abs/1604.07200.
  8. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  9. Satyanarayana V. Lokam. Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science, 4(1&2):1-155, January 2009. URL: http://dx.doi.org/10.1561/0400000011.
  10. Benjian Lv and Kaishun Wang. The eigenvalues of q-Kneser graphs. Discrete Mathematics, 312(6):1144-1147, 2012. URL: http://dx.doi.org/10.1016/j.disc.2011.11.042.
  11. E. I. Nečiporuk. On a boolean function. Doklady of the Academy of Sciences of the USSR, 164(4):765-766, 1966. Google Scholar
  12. P. Pudlák and V. Rödl. A combinatorial approach to complexity. Combinatorica, 12:221-226, 1992. URL: http://dx.doi.org/10.1007/BF01204724.
  13. P. Pudlák and V. Rödl. Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics, 136(1-3):253-279, dec 1994. URL: http://dx.doi.org/10.1016/0012-365x(94)00115-y.
  14. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):17:1-17:24, September 2008. Google Scholar
  15. Lajos Rónyai, László Babai, and Murali K. Ganapathy. On the number of zero-patterns of a sequence of polynomials. Journal of the AMS, 14:2001, 2002. Google Scholar
  16. Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer New York Inc., 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