Any monotone property of 3-uniform hypergraphs is weakly evasive

Kulkarni, R; Qiao, Y; Sun, X

Any monotone property of 3-uniform hypergraphs is weakly evasive

Kulkarni, R Qiao, Y

Sun, X

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7876 LNCS pp. 224 - 235
Issue Date:: 2013-01-01

Closed Access

	Filename	Description	Size
	2013005434OK.pdf		230.47 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Kulkarni, R	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.contributor.author	Sun, X	en_US
dc.date.issued	2013-01-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7876 LNCS pp. 224 - 235	en_US
dc.identifier.isbn	9783642382352	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28940
dc.description.abstract	For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [18] show that any non-constant monotone property P: {0,1} (2n) → {0,1} of n-vertex graphs has D(P) = Ω (n). We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P: {0,1} (3n) → {0,1} of n-vertex 3-uniform hypergraphs has D(P) = Ω (n). Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant. Interestingly, our proof makes use of Vinogradov's Theorem (weak Gold-bach Conjecture), inspired by its recent use by Babai et. al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question. © Springer-Verlag Berlin Heidelberg 2013.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-38236-9_21	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Any monotone property of 3-uniform hypergraphs is weakly evasive	en_US
dc.type	Conference Proceeding
utslib.citation.volume	7876 LNCS	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
dc.location.activity	Hong Kong	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	7876 LNCS	en_US

Abstract:

For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [18] show that any non-constant monotone property P: {0,1} (2n) → {0,1} of n-vertex graphs has D(P) = Ω (n). We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P: {0,1} (3n) → {0,1} of n-vertex 3-uniform hypergraphs has D(P) = Ω (n). Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant. Interestingly, our proof makes use of Vinogradov's Theorem (weak Gold-bach Conjecture), inspired by its recent use by Babai et. al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question. © Springer-Verlag Berlin Heidelberg 2013.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28940