A Generalization and Proof of the Aanderaa-Rosenberg Conjecture

A Generalization and Proof of the Aanderaa-Rosenberg Conjecture. Rivest, R. L. & Vuillemin, J. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, of STOC '75, pages 6–11, New York, NY, USA, 1975. ACM.

Paper doi abstract bibtex

We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)&equil;d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.

@inproceedings{rivest_generalization_1975,
	address = {New York, NY, USA},
	series = {{STOC} '75},
	title = {A {Generalization} and {Proof} of the {Aanderaa}-{Rosenberg} {Conjecture}},
	url = {http://doi.acm.org/10.1145/800116.803747},
	doi = {10.1145/800116.803747},
	abstract = {We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)\&equil;d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.},
	urldate = {2017-12-18TZ},
	booktitle = {Proceedings of the {Seventh} {Annual} {ACM} {Symposium} on {Theory} of {Computing}},
	publisher = {ACM},
	author = {Rivest, Ronald L. and Vuillemin, Jean},
	year = {1975},
	pages = {6--11}
}

Downloads: 0

{"_id":"8hewXyyQHPW4PYgvC","bibbaseid":"rivest-vuillemin-ageneralizationandproofoftheaanderaarosenbergconjecture-1975","downloads":0,"creationDate":"2018-08-26T16:08:16.489Z","title":"A Generalization and Proof of the Aanderaa-Rosenberg Conjecture","author_short":["Rivest, R. L.","Vuillemin, J."],"year":1975,"bibtype":"inproceedings","biburl":"https://api.zotero.org/users/4543350/collections/8WTCDAGM/items?key=fF5y8imNS4C1ujxzFy92dlmr&format=bibtex&limit=100","bibdata":{"bibtype":"inproceedings","type":"inproceedings","address":"New York, NY, USA","series":"STOC '75","title":"A Generalization and Proof of the Aanderaa-Rosenberg Conjecture","url":"http://doi.acm.org/10.1145/800116.803747","doi":"10.1145/800116.803747","abstract":"We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)&equil;d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.","urldate":"2017-12-18TZ","booktitle":"Proceedings of the Seventh Annual ACM Symposium on Theory of Computing","publisher":"ACM","author":[{"propositions":[],"lastnames":["Rivest"],"firstnames":["Ronald","L."],"suffixes":[]},{"propositions":[],"lastnames":["Vuillemin"],"firstnames":["Jean"],"suffixes":[]}],"year":"1975","pages":"6–11","bibtex":"@inproceedings{rivest_generalization_1975,\n\taddress = {New York, NY, USA},\n\tseries = {{STOC} '75},\n\ttitle = {A {Generalization} and {Proof} of the {Aanderaa}-{Rosenberg} {Conjecture}},\n\turl = {http://doi.acm.org/10.1145/800116.803747},\n\tdoi = {10.1145/800116.803747},\n\tabstract = {We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)\\&equil;d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.},\n\turldate = {2017-12-18TZ},\n\tbooktitle = {Proceedings of the {Seventh} {Annual} {ACM} {Symposium} on {Theory} of {Computing}},\n\tpublisher = {ACM},\n\tauthor = {Rivest, Ronald L. and Vuillemin, Jean},\n\tyear = {1975},\n\tpages = {6--11}\n}\n\n","author_short":["Rivest, R. L.","Vuillemin, J."],"key":"rivest_generalization_1975","id":"rivest_generalization_1975","bibbaseid":"rivest-vuillemin-ageneralizationandproofoftheaanderaarosenbergconjecture-1975","role":"author","urls":{"Paper":"http://doi.acm.org/10.1145/800116.803747"},"downloads":0},"search_terms":["generalization","proof","aanderaa","rosenberg","conjecture","rivest","vuillemin"],"keywords":[],"authorIDs":[],"dataSources":["WGuzu8d9YYFsR6WY7"]}