Document Open Access Logo

Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Authors Tomer Grossman, Ilan Komargodski, Moni Naor

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.56.pdf
  • Filesize: 0.79 MB
  • 38 pages

Document Identifiers

Author Details

Tomer Grossman
  • Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
Ilan Komargodski
  • NTT Research, Palo Alto, CA, USA
Moni Naor
  • Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

Funding

  • Grossman, Tomer: Israel Science Foundation (no. 950/16).
  • Komargodski, Ilan: AFOSR grant FA9550-15-1-0262, Israel Science Foundation (no. 950/16), and a Levzion Fellowship.
  • Naor, Moni: Israel Science Foundation (no. 950/16).

Acknowledgements

We thank Scott Aaronson for discussions on quantum certificates, Ron Fagin for useful comments, and Ofer Grossman for helpful discussions and Yoram Moses and Benny Applebaum for suggesting instance optimality in other settings. We thank some of the referees of the paper for helpful comments.

Cite AsGet BibTex

Tomer Grossman, Ilan Komargodski, and Moni Naor. Instance Complexity and Unlabeled Certificates in the Decision Tree Model. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 56:1-56:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.56

Abstract

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively. We initiate the systematic study of instance complexity and optimality in the query model (a.k.a. the decision tree model). In this model, instance optimality of an algorithm for computing a function is the requirement that the complexity of an algorithm on any input is at most a constant factor larger than the complexity of the best correct algorithm. That is we compare the decision tree to one that receives a certificate and its complexity is measured only if the certificate is correct (but correctness should hold on any input). We study both deterministic and randomized decision trees and provide various characterizations and barriers for more general results. We introduce a new measure of complexity called unlabeled-certificate complexity, appropriate for graph properties and other functions with symmetries, where only information about the structure of the graph is known to the competing algorithm. More precisely, the certificate is some permutation of the input (rather than the input itself) and the correctness should be maintained even if the certificate is wrong. First we show that such an unlabeled certificate is sometimes very helpful in the worst-case. We then study instance optimality with respect to this measure of complexity, where an algorithm is said to be instance optimal if for every input it performs roughly as well as the best algorithm that is given an unlabeled certificate (but is correct on every input). We show that instance optimality depends on the group of permutations in consideration. Our proofs rely on techniques from hypothesis testing and analysis of random graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • decision tree complexity
  • instance complexity
  • instance optimality
  • query complexity
  • unlabeled certificates

Metrics

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

References

  1. Scott Aaronson. Quantum certificate complexity. J. Comput. Syst. Sci., 74(3):313-322, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.020.
  2. Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-Optimal Geometric Algorithms. J. ACM, 64(1):3:1-3:38, 2017. URL: https://doi.org/10.1145/3046673.
  3. Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A Combinatorial Characterization of the Testable Graph Properties: It’s All About Regularity. SIAM J. Comput., 39(1):143-167, 2009. Google Scholar
  4. Noga Alon and Joel Spencer. The Probabilistic Method. John Wiley, third edition, 2008. Google Scholar
  5. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. J. ACM, 64(5):32:1-32:24, 2017. Google Scholar
  6. Andris Ambainis and Xiaoming Sun. New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC), 18:116, 2011. Google Scholar
  7. Ilya Baran and Erik D. Demaine. Optimal adaptive algorithms for finding the nearest and farthest point on a parametric black-box curve. In Proceedings of the 20th ACM Symposium on Computational Geometry, SOCG, pages 220-229. ACM, 2004. Google Scholar
  8. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. Google Scholar
  9. R. Best, P. van Emde Boas, and H.W. Lenstra. A Sharpened Version of the Aanderaa-Rosenberg Conjecture. Mathematisch Centrum Amsterdam. Afdeling Zuivere Wiskunde: ZW. Stichting Mathematisch Centrum, 1974. URL: http://books.google.co.il/books?id=9KLcHAAACAAJ.
  10. Manuel Blum and Russell Impagliazzo. Generic Oracles and Oracle Classes (Extended Abstract). In 28th Annual Symposium on Foundations of Computer Science, FOCS, pages 118-126. IEEE Computer Society, 1987. Google Scholar
  11. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  12. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  13. Amit Chakrabarti and Subhash Khot. Improved lower bounds on the randomized complexity of graph properties. Random Struct. Algorithms, 30(3):427-440, 2007. Google Scholar
  14. Stephen A. Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM J. Comput., 15(1):87-97, 1986. Google Scholar
  15. Constantinos Daskalakis and Yasushi Kawase. Optimal Stopping Rules for Sequential Hypothesis Testing. In 25th Annual European Symposium on Algorithms, ESA, pages 32:1-32:14, 2017. Google Scholar
  16. Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Patrascu. The geometry of binary search trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 496-505, 2009. Google Scholar
  17. Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. Adaptive set intersections, unions, and differences. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 743-752. ACM/SIAM, 2000. Google Scholar
  18. Cynthia Dwork and Yoram Moses. Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures. Inf. Comput., 88(2):156-186, 1990. URL: https://doi.org/10.1016/0890-5401(90)90014-9.
  19. Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci., 66(4):614-656, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00026-6.
  20. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Limit on the Speed of Quantum Computation in Determining Parity. Phys. Rev. Lett., 81:5442-5444, December 1998. Google Scholar
  21. Amos Fiat and Gerhard J. Woeginger, editors. Online Algorithms, The State of the Art (the book grow out of a Dagstuhl Seminar, June 1996), volume 1442 of Lecture Notes in Computer Science. Springer, 1998. URL: https://doi.org/10.1007/BFb0029561.
  22. Eldar Fischer and Arie Matsliah. Testing Graph Isomorphism. SIAM J. Comput., 38(1):207-225, 2008. Google Scholar
  23. Alan M. Frieze and Michal Karonski. Introduction to Random Graphs. Cambridge University Press, 2015. URL: https://doi.org/10.1017/CBO9781316339831.
  24. Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some boolean function complexity measures. Combinatorica, 36(3):265-311, June 2016. URL: https://doi.org/10.1007/s00493-014-3189-x.
  25. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  26. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property Testing and its Connection to Learning and Approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  27. Oded Goldreich and Dana Ron. Algorithmic Aspects of Property Testing in the Dense Graphs Model. In Property Testing - Current Research and Surveys, pages 295-305. Springer, 2010. Google Scholar
  28. Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for BPP. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 132-143. IEEE Computer Society, 2017. Google Scholar
  29. Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212-219. ACM, 1996. Google Scholar
  30. Péter Hajnal. An Ω(n^4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11(2):131-143, 1991. Google Scholar
  31. Joseph Y. Halpern, Yoram Moses, and Orli Waarts. A Characterization of Eventual Byzantine Agreement. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pages 333-346. ACM, 1990. Google Scholar
  32. Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. CoRR, abs/1907.00847, 2019. URL: http://arxiv.org/abs/1907.00847.
  33. Rahul Jain and Shengyu Zhang. The Influence Lower Bound Via Query Elimination. Theory of Computing, 7(1):147-153, 2011. Google Scholar
  34. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer Berlin Heidelberg, 2012. Google Scholar
  35. Jeff Kahn, Michael E. Saks, and Dean Sturtevant. A topological approach to evasiveness. Combinatorica, 4(4):297-306, 1984. Google Scholar
  36. Valerie King. An Ω(n^5/4) lower bound on the randomized complexity of graph properties. Combinatorica, 11(1):23-32, 1991. Google Scholar
  37. Silvio Micali and Rafael Pass. Local zero knowledge. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC, pages 306-315. ACM, 2006. Revision URL: http://www.cs.cornell.edu/~rafael/papers/preciseZK.pdf.
  38. Yoram Moses and Mark R. Tuttle. Programming Simultaneous Actions Using Common Knowledge. Algorithmica, 3:121-169, 1988. Google Scholar
  39. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. In Allen B. Tucker, editor, The Computer Science and Engineering Handbook, pages 141-161. CRC Press, 1997. Google Scholar
  40. Noam Nisan. CREW prams and decision trees. SIAM J. Comput., 20(6):999-1007, 1991. Google Scholar
  41. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  42. Pekka Orponen, Ker-I Ko, Uwe Schöning, and Osamu Watanabe. Instance Complexity. J. ACM, 41(1):96-121, 1994. URL: https://doi.org/10.1145/174644.174648.
  43. Ran Raz and Pierre McKenzie. Separation of the Monotone NC Hierarchy. Combinatorica, 19(3):403-435, 1999. Google Scholar
  44. Ronald L. Rivest and Jean Vuillemin. A Generalization and Proof of the Aanderaa-Rosenberg Conjecture. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, STOC, pages 6-11. ACM, 1975. Google Scholar
  45. David Rubinstein. Sensitivity vs. Block Sensitivity of Boolean Functions. Combinatorica, 15(2):297-299, 1995. Google Scholar
  46. Michael Saks and Avi Wigderson. Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. In 27th Annual Symposium on Foundations of Computer Science, SFCS '86, pages 29-38. IEEE Computer Society, 1986. URL: https://doi.org/10.1109/SFCS.1986.44.
  47. Daniel Dominic Sleator and Robert Endre Tarjan. Self-Adjusting Binary Search Trees. J. ACM, 32(3):652-686, 1985. URL: https://doi.org/10.1145/3828.3835.
  48. Avishay Tal. Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science, ITCS, pages 441-454. ACM, 2013. Google Scholar
  49. Gábor Tardos. Query complexity, or why is it difficult to seperate NP^A∩ coNP^A from P^A by random oracles A? Combinatorica, 9(4):385-392, 1989. Google Scholar
  50. Gregory Valiant and Paul Valiant. Instance optimal learning of discrete distributions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 142-155. ACM, 2016. Google Scholar
  51. Gregory Valiant and Paul Valiant. An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM J. Comput., 46(1):429-455, 2017. Google Scholar
  52. Andrew Chi-Chih Yao. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science, FOCS, pages 222-227. IEEE Computer Society, 1977. Google Scholar
  53. Andrew Chi-Chih Yao. Lower Bounds to Randomized Algorithms for Graph Properties. J. Comput. Syst. Sci., 42(3):267-287, 1991. 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