Paper Info
Title
On the Power of Parity Queries in Boolean Decision Trees.
Abstract
In an influential paper, Kushilevitz and Mansour (1993) introduced a natural extension of Boolean decision trees called parity decision tree (PDT) where one may query the sum modulo 2, i. e., the parity, of an arbitrary subset of variables. Although originally introduced in the context of learning, parity decision trees have recently regained interest in the context of communication complexity (cf. Shi and Zhang 2010) and property testing (cf. Bhrushundi, Chakraborty, and Kulkarni 2013). In this paper, we investigate the power of parity queries. In particular, we show that the parity queries can be replaced by ordinary ones at the cost of the total influence aka average sensitivity per query. Our simulation is tight as demonstrated by the parity function. At the heart of our result lies a qualitative extension of the result of O'Donnell, Saks, Schramme, and Servedio (2005) titled: Every decision tree has an influential variable. Recently Jain and Zhang (2011) obtained an alternate proof of the same. Our main contribution in this paper is a simple but surprising observation that the query elimination method of Jain and Zhang can indeed be adapted to eliminate, seemingly much more powerful, parity queries. Moreover, we extend our result to linear queries for Boolean valued functions over arbitrary finite fields.
Year
DOI
Venue
2015
10.1007/978-3-319-17142-5_10
Lecture Notes in Computer Science
Field
DocType
Volume
Boolean function,Discrete mathematics,Decision tree,Combinatorics,Property testing,Parity function,Decision tree model,Communication complexity,Standard Boolean model,Parity (mathematics),Mathematics
Conference
9076
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
26
3
Name
Order
Citations
PageRank
Raghav Kulkarni117219.48
Youming Qiao29715.55
Xiaoming Sun328041.19