Author name cluster

Jinyu Xie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

STOC Conference 2018 Conference Paper

Distribution-free junta testing

Zhengyang Liu 0002
Xi Chen 0001
Rocco A. Servedio
Ying Sheng 0004
Jinyu Xie

We study the problem of testing whether an unknown n -variable Boolean function is a k -junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1} n . Our first main result is that distribution-free k -junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ( k 2 )/є queries (independent of n ). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k -junta testing algorithm must make Ω(2 k /3 ) queries even to test to accuracy є=1/3. These bounds establish that while the optimal query complexity of non-adaptive k -junta testing is 2 Θ( k ) , for adaptive testing it is poly( k ), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

Details

STOC Conference 2017 Conference Paper

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Xi Chen 0001
Erik Waingarten
Jinyu Xie

We prove a lower bound of Ω( n 1/3 ) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f :{0,1} n → {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω( n 1/4 ) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs. Beyond monotonicity we prove a lower bound of Ω(√ n ) for two-sided, adaptive algorithms and a lower bound of Ω( n ) for one-sided, non-adaptive algorithms for testing unateness, a natural generalization of monotonicity. The latter matches the linear upper bounds by Khot and Shinkar (RANDOM'16) and by Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri (2017).

Details

FOCS Conference 2017 Conference Paper

Boolean Unateness Testing with Õ(n 3/4 ) Adaptive Queries

Xi Chen 0001
Erik Waingarten
Jinyu Xie

We give an adaptive algorithm that tests whether an unknown Boolean function f: {0, 1} n → {0, 1} is unate (i. e. every variable of f is either non-decreasing or non-increasing) or ε-far from unate with one-sided error and Õ(n 3/4 /ϵ 2 ) many queries. This improves on the best adaptive O(n/ϵ)-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri [1] when 1/ϵ 1/4. Combined with the Ω̃(n)query lower bound for non-adaptive algorithms with one-sided error of [2], [3], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.

Details

SODA Conference 2016 Conference Paper

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

Xi Chen 0001
Jinyu Xie

We improve both upper and lower bounds for the distribution-free testing of monotone conjunctions. Given oracle access to an unknown Boolean function f: {0, 1} n → {0, 1} and sampling oracle access to an unknown distribution over {0, 1} n, we present an Õ ( n 1/3 /∊ 5 )-query algorithm that tests whether f is a monotone conjunction versus ∊-far from any monotone conjunction with respect to. This improves the previous best upper bound of Õ ( n 1/2 /∊) by Dolev and Ron [DR11], when 1/∊ is small compared to n. For some constant ∊ 0 > 0, we also prove a lower bound of for the query complexity, improving the previous best lower bound of by Glasner and Servedio [GS09]. Our upper and lower bounds are tight, up to a polylogarithmic factor, when the distance parameter ∊ is a constant. Furthermore, the same upper and lower bounds can be extended to the distribution-free testing of general conjunctions, and the lower bound can be extended to that of decision lists and linear threshold functions.

Details