Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

Authors Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.17.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Nikhil Balaji
Samir Datta
Raghav Kulkarni
Supartha Podder

Cite AsGet BibTex

Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder. Graph Properties in Node-Query Setting: Effect of Breaking Symmetry. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.17

Abstract

The query complexity of graph properties is well-studied when queries are on the edges. We investigate the same when queries are on the nodes. In this setting a graph G = (V,E) on n vertices and a property P are given. A black-box access to an unknown subset S of V is provided via queries of the form "Does i belong to S?". We are interested in the minimum number of queries needed in the worst case in order to determine whether G[S] - the subgraph of G induced on S - satisfies P. Our primary motivation to study this model comes from the fact that it allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on the hereditary graph properties - properties that are closed under deletion of vertices as well as edges. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on G, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., n. We show that in the absence of any symmetry on G it can fall as low as O(n^{1/(d + 1)}) where d denotes the minimum possible degree of a minimal forbidden sub-graph for P. In particular, every hereditary property benefits at least quadratically. The main question left open is: Can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with finitely many forbidden subgraphs by exhibiting a bound of Omega(n^{1/k}) for a constant k depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing Omega(log(n)*log(log(n))) bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdos and Rado.
Keywords
  • query complexity
  • graph properties
  • symmetry and computation
  • forbidden subgraph

Metrics

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

References

  1. Wikipedia - Abel-Ruffini Theorem. Google Scholar
  2. Laszlo Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the distribution of prime numbers. arXiv preprint arXiv:1001.4829, 2010. Google Scholar
  3. Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder. Graph properties in node-query setting: effect of breaking symmetry. CoRR, abs/1510.08267, 2015. URL: http://arxiv.org/abs/1510.08267.
  4. Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni. Property testing bounds for linear and quadratic functions via parity decision trees. In Computer Science-Theory and Applications, pages 97-110. Springer, 2014. Google Scholar
  5. Timothy Black. Monotone properties of k-uniform hypergraphs are weakly evasive. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 383-391. ACM, 2015. Google Scholar
  6. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. Google Scholar
  7. Amit Chakrabarti, Subhash Khot, and Yaoyun Shi. Evasiveness of subgraph containment and related properties. SIAM Journal on Computing, 31(3):866-875, 2001. Google Scholar
  8. Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. In Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on, pages 163-167. IEEE, 2005. Google Scholar
  9. Paul Erdös and Richard Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 1(1):85-90, 1960. Google Scholar
  10. Ehud Friedgut, Jeff Kahn, and Avi Wigderson. Computing graph properties by randomized subcube partitions. In Randomization and approximation techniques in computer science, pages 105-113. Springer, 2002. Google Scholar
  11. Chris Godsil and Gordon F Royle. Algebraic graph theory, volume 207. Springer Science &Business Media, 2013. Google Scholar
  12. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 4:1-27, 2011. Google Scholar
  13. Russell Impagliazzo and Moni Naor. Decision trees and downward closures. In Structure in Complexity Theory Conference, pages 29-38, 1988. Google Scholar
  14. Gabör Ivanyos. Personal communication. Google Scholar
  15. Jeff Kahn, Michael Saks, and Dean Sturtevant. A topological approach to evasiveness. Combinatorica, 4(4):297-306, 1984. Google Scholar
  16. Raghav Kulkarni. Evasiveness through a circuit lens. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 139-144. ACM, 2013. Google Scholar
  17. Raghav Kulkarni. Gems in decision tree complexity revisited. ACM SIGACT News, 44(3):42-55, 2013. Google Scholar
  18. Raghav Kulkarni, Youming Qiao, and Xiaoming Sun. Any monotone property of 3-uniform hypergraphs is weakly evasive. Theoretical Computer Science, 588:16 - 23, 2015. URL: http://www.sciencedirect.com/science/article/pii/S030439751400855X, URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.tcs.2014.11.012.
  19. Raghav Kulkarni and Miklos Santha. Query complexity of matroids. In Algorithms and Complexity, pages 300-311. Springer, 2013. Google Scholar
  20. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 455-464, New York, NY, USA, 1991. ACM. URL: http://doi.acm.org/10.1145/103418.103466, URL: http://dx.doi.org/10.1145/103418.103466.
  21. Frank H. Lutz. Some results related to the evasiveness conjecture. Journal of Combinatorial Theory, Series B, 81(1):110 - 124, 2001. URL: http://www.sciencedirect.com/science/article/pii/S0095895600920008, URL: http://dx.doi.org/http://dx.doi.org/10.1006/jctb.2000.2000.
  22. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  23. Ronald L Rivest and Jean Vuillemin. On recognizing graph properties from adjacency matrices. Theoretical Computer Science, 3(3):371-384, 1976. Google Scholar
  24. Xiaoming Sun, Andrew C Yao, and Shengyu Zhang. Graph properties and circular functions: How low can quantum query complexity go? In Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on, pages 286-293. IEEE, 2004. Google Scholar
  25. Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of boolean functions. Theoretical Computer Science, 411(26):2612-2618, 2010. 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