Article

Free access

Lower bounds on the complexity of graph properties

Author:

Valerie KingAuthors Info & Claims

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

Pages 468 - 476

https://doi.org/10.1145/62212.62258

Published: 01 January 1988 Publication History

PDF eReader

Abstract

In this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, …, n} has a given property by asking questions of the form “Is edge <i,j> in the graph?”. The complexity of a property is the number of questions which must be asked in the worst case.

Aanderaa and Rosenberg conjectured that any monotone, nontrivial, (isomorphism-invariant) n-node digraph property has complexity Ω(n²). This bound was proved by Rivest and Vuillemin and subsequently improved to n²/4+ο(n²). In Part I, we give a bound of n²/2+ο(n²). Whether these properties are evasive remains open.

In Part II, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next edge to be queried. Yao's lower bound on the randomized complexity of any monotone nontrivial graph property is improved from Ω(nlog^1/12n) to Ω(n^5/4), and improved bounds for the complexity of monotone, nontrivial bipartite graph properties are shown.

References

[1]

G. H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, 1938.

Google Scholar

[2]

J. Kahn, M. $aks, and D. Sturtevant, A topological approach to evasiveness, Combinatorica 4 (1984), pp. 297-306.

Crossref

Google Scholar

[3]

D.J. Kieitman and D.J. Kwiatkowski, Further results on the Aanderaa- Rosenberg Conjecture, Y. Combinatorial Theory Ser. B 28 (1980) pp.85-95.

Crossref

Google Scholar

[4]

R. Oliver, Fixed-point sets of group actions on finite acyclic complexes, Comment. Math. Helv. 50 (1975) 15,5- 177.

Crossref

Google Scholar

[5]

R. Rive~;t and S. Vuillemin, On recognizing graph properties from adjacency matrices, Theor. Comp. Sci. 3 (1976) pp.371-384.

Crossref

Google Scholar

[6]

A.L. Rosenberg, On the time required to recognize properties of graphs: A problem. SIG ACT News 5 (g) (1973), pp.15-16.

Digital Library

Google Scholar

[7]

N. Saner and J. Spencer, Edge-disjoint placement of graphs, J. Combinatorial Theory, Ser.B 25, {1978) pp.295-302.

Google Scholar

[8]

P.A. Smith, Fixed point theorems for periodic transformations, Amer. J. of ~{a t h. 65' (1941 ), 1-8.

Google Scholar

[9]

P. Turin, On the theory of graphs, Colloq. Math g (1954) pp.19-30.

Google Scholar

[10]

A. Yao, Probabilistic computations' towards a unified measure of complexity, Proc. 18th Annual Symposium on the Foundations of Computer Science, (1977), pp.222-227.

Digital Library

Google Scholar

[11]

A. Yao, Lower Bounds to Randomized Algorithms for Graph Properties, Proc. ~gth Annual Symposium on the Faundationa of Computer Science, (1987), pp.393-400.

Google Scholar

[12]

A. Yao, Monotone Bipartite Graph Properties Are Evasive (unpublished), (x0s6).

Google Scholar

Cited By

View all

Maiti ADey P(2024)Query Complexity of Tournament SolutionsTheoretical Computer Science10.1016/j.tcs.2024.114422(114422)Online publication date: Jan-2024
https://doi.org/10.1016/j.tcs.2024.114422
Aaronson SBen-David SKothari RRao STal AKhuller SVassilevska Williams V(2021)Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theoremProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451047(1330-1342)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451047
Casteigts ADubois SPetit FRobson J(2019)Robustness: A new form of heredity motivated by dynamic networksTheoretical Computer Science10.1016/j.tcs.2019.08.008Online publication date: Aug-2019
https://doi.org/10.1016/j.tcs.2019.08.008
Show More Cited By

Index Terms

Lower bounds on the complexity of graph properties
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Lower bounds on the complexity of graph properties
Complexity Lower Bounds through Balanced Graph Properties
CCC '12: Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC)

We present a combinatorial approach for proving complexity lower bounds, we focus on the following instantiation of this approach. For a property of regular hyper graphs with $m$ edges and an arbitrary hyper graph $G$ with $m-t$ edges, we may count the ...
On the sensitivity complexity of bipartite graph properties

Sensitivity complexity, introduced by Cook, Dwork, and Reischuk (1982, 1986) in [2,3], is an important complexity measure of Boolean functions. Turan (1984) [7] initiated the study of sensitivity complexity for graph properties. He conjectured that for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

January 1988

553 pages

ISBN:0897912640

DOI:10.1145/62212

Chairman:
J'anos Simon
Univ. of Chicago, Illinois

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC88

Sponsor:

SIGACT

STOC88: 1988 Symposium on the Theory of Computing

May 2 - 4, 1988

Illinois, Chicago, USA

Acceptance Rates

STOC '88 Paper Acceptance Rate 53 of 192 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
436
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Maiti ADey P(2024)Query Complexity of Tournament SolutionsTheoretical Computer Science10.1016/j.tcs.2024.114422(114422)Online publication date: Jan-2024
https://doi.org/10.1016/j.tcs.2024.114422
Aaronson SBen-David SKothari RRao STal AKhuller SVassilevska Williams V(2021)Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theoremProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451047(1330-1342)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451047
Casteigts ADubois SPetit FRobson J(2019)Robustness: A new form of heredity motivated by dynamic networksTheoretical Computer Science10.1016/j.tcs.2019.08.008Online publication date: Aug-2019
https://doi.org/10.1016/j.tcs.2019.08.008
Dey PSingh SMarkovitch S(2017)Query complexity of tournament solutionsProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298483.3298669(2992-2998)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298483.3298669
Procaccia A(2008)A note on the query complexity of the Condorcet winner problemInformation Processing Letters10.1016/j.ipl.2008.07.012108:6(390-393)Online publication date: 20-Nov-2008
https://dl.acm.org/doi/10.1016/j.ipl.2008.07.012
Chakrabarti AKhot S(2007)Improved lower bounds on the randomized complexity of graph propertiesRandom Structures & Algorithms10.1002/rsa.2016430:3(427-440)Online publication date: 8-Feb-2007
https://doi.org/10.1002/rsa.20164
Santha M(2006)On the Monte carlo boolean decision tree complexity of read‐once formulaeRandom Structures & Algorithms10.1002/rsa.32400601086:1(75-87)Online publication date: 11-Oct-2006
https://doi.org/10.1002/rsa.3240060108
O'Donnell RSaks MSchramm O(2005)Every decision tree has an in.uential variableProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science10.1109/SFCS.2005.34(31-39)Online publication date: 23-Oct-2005
https://dl.acm.org/doi/10.1109/SFCS.2005.34
Buhrman Hde Wolf R(2002)Complexity measures and decision tree complexityTheoretical Computer Science10.1016/S0304-3975(01)00144-X288:1(21-43)Online publication date: 9-Oct-2002
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900144-X
Friedgut EKahn JWigderson A(2002)Computing Graph Properties by Randomized Subcube PartitionsRandomization and Approximation Techniques in Computer Science10.1007/3-540-45726-7_9(105-113)Online publication date: 23-Aug-2002
https://doi.org/10.1007/3-540-45726-7_9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Lower bounds on the complexity of graph properties

Complexity Lower Bounds through Balanced Graph Properties

On the sensitivity complexity of bipartite graph properties