Abstract
We determine the complexity of evaluating monotone Boolean functions in a variant of the decision tree model introduced in [Charikar et al. 2002]. In this model, reading different variables can incur different costs, and competitive analysis is employed to evaluate the performance of the algorithms. It is known that for a monotone Boolean function f, the size of the largest certificate, aka PROOF(f), is a lower bound for γ(f), the best possible competitiveness achievable by an algorithm on f. This bound has been proved to be achievable for some subclasses of the monotone Boolean functions, e.g., read once formulae, threshold trees. However, determining γ(f) for an arbitrary monotone Boolean function has so far remained a major open question, with the best known upper bound being essentially a factor of 2 away from the above lower bound.
We close the gap and prove that for any monotone Boolean function f, γ(f) = PROOF(f). In fact, we prove that γ(f) ≤ PROOF(f) holds for a class much larger than the set of monotone Boolean functions. This class also contains all Boolean functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boros, E., Ünlüyurt, T.: Diagnosing double regular systems. Annals of Mathematics and Artificial Intelligence 26(1-4), 171–191 (1999)
Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288(1), 21–43 (2002)
Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J.M., Raghavan, P., Sahai, A.: Query strategies for priced information. Journal of Computer and System Sciences 64(4), 785–819 (2002)
Cicalese, F., Laber, E.S.: A new strategy for querying priced information. In: Proc. of STOC 2005, pp. 674–683. ACM Press, New York (2005)
Cicalese, F., Laber, E.S.: An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 664–676. Springer, Heidelberg (2005)
Cicalese, F., Laber, E.S.: On the competitive ratio of evaluating priced functions. In: Proc. of SODA 2006, pp. 944–953 (2006)
Duffuaa, S.O., Raouf, A.: An optimal sequence in multicharacteristics inspection. J. Optim. Theory Appl. 67(1), 79–86 (1990)
Gillies, D.W.: Algorithms to schedule tasks with and/or precedence constraints. PhD thesis, Champaign, IL, USA (1993)
Graham, R.L., Grötschel, M., Lovász, L. (eds.): Handbook of Combinatorics. The Mit Press - North-Holland (1996)
Greiner, R., Hayward, R., Jankowska, M., Molloy, M.: Finding optimal satisficing strategies for and-or trees. Artificial Intelligence 170(1), 19–58 (2006)
Gupta, A., Kumar, A.: Sorting and selection with structured costs. In: Proc. of FOCS 2001, pp. 416–425. IEEE, Los Alamitos (2001)
Heiman, R., Newman, I., Wigderson, A.: On read-once threshold formulae and their randomized decision tree complexity. TCS 107(1), 63–76 (1993)
Heiman, R., Wigderson, A.: Randomized vs. deterministic decision tree complexity for read-once boolean functions. Comput. Complexity 1, 311–329 (1991)
Hellerstein, J.M.: Optimization techniques for queries with expensive methods. ACM Transactions on Database Systems 23(2), 113–157 (1998)
Kannan, S., Khanna, S.: Selection with monotone comparison cost. In: Proc. of SODA 2003, pp. 10–17. ACM/SIAM (2003)
Louis AnthonyCox, J., Qiu, Y., Kuehner, W.: Heuristic least-cost computation of discrete classification functions with uncertain argument values. Ann. Oper. Res. 21(1-4), 1–30 (1989)
Qiu, Y., Anthony Cox Jr., L., Davis, L.: Guess-and-verify heuristics for reducing uncertainties in expert classification systems. In: Dubois, D., Wellman, M.P. (eds.) UAI, pp. 252–258. Morgan Kaufmann, San Francisco (1992)
Rivest, R.L., Vuillemin, J.: On recognizing graph properties from adjacency matrices. TCS 3(3), 371–384 (1976)
Saks, M., Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In: Proc. of FOCS 1986, pp. 29–38. IEEE, Los Alamitos (1986)
Snir, M.: Lower bounds on probabilistic linear decision trees. TCS 38, 69–82 (1985)
Tarsi, M.: Optimal search on some game trees. JACM 30(3), 389–396 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cicalese, F., Laber, E.S. (2008). Function Evaluation Via Linear Programming in the Priced Information Model. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, vol 5125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70575-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-70575-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70574-1
Online ISBN: 978-3-540-70575-8
eBook Packages: Computer ScienceComputer Science (R0)