67 citations
- Rutgers, The State University of New JerseyUS9 papers
- Columbia UniversityUS3 papers
- Eindhoven University of TechnologyNL3 papers
- Centre National de la Recherche ScientifiqueFR2 papers
- Georgia Institute of TechnologyUS2 papers
- Université Paris CitéFR2 papers
- University of WaterlooCA2 papers
- Bar-Ilan UniversityIL1 paper
- Beijing Institute of TechnologyCN1 paper
- Boston UniversityUS1 paper
- Central University of KeralaIN1 paper
- Christ UniversityIN1 paper
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2014★ 2 cited
Boolean function monotonicity testing requires (almost) non-adaptive queries
Xi Chen, Anindya De, Rocco A. Servedio +1
We prove a lower bound of , for all , on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an -variable Boolean function…
cs.CC2013★ 1 cited
Every locally characterized affine-invariant property is testable
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami +2
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove th…