Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > XI CHEN:
All reports by Author Xi Chen:

TR26-312 | 5th November 2026
Clement Canonne, Xi Chen, William Pires, Toniann Pitassi, Rocco Servedio

The Space Complexity of Property Testing

We initiate the study of the space complexity of property testing. We focus on five properties of Boolean functions that have been intensively studied in the property testing literature: monotonicity, symmetry, linearity, being a junta, and being a linear threshold function.

On the upper bounds side, we show --- ... more >>>


TR26-231 | 6th October 2026
Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis

Tarski Fixed Points in Quasi-FPT Queries

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$,
$$
\Omega\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le
more >>>


TR24-057 | 28th March 2024
Xi Chen, Yuhao Li, Mihalis Yannakakis

Computing a Fixed Point of Contraction Maps in Polynomial Queries

Revisions: 1

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.

more >>>

TR23-073 | 15th May 2023
Xi Chen, Yuhao Li, Mihalis Yannakakis

Reducing Tarski to Unique Tarski (in the Black-box Model)

We study the problem of finding a Tarski fixed point over the $k$-dimensional grid $[n]^k$. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>


TR19-165 | 18th November 2019
Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>


TR17-068 | 20th April 2017
Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

Settling the query complexity of non-adaptive junta testing

We prove that any non-adaptive algorithm that tests whether an unknown
Boolean function $f\colon \{0, 1\}^n\to\{0, 1\} $ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ... more >>>


TR16-065 | 18th April 2016
Xi Chen, Yu Cheng, Bo Tang

A Note on Teaching for VC Classes

Revisions: 1

In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of $C \subseteq \{0,1\}^n$, denoted by $VCD(C)$, is the maximum size of a shattered subset of $[n]$, where $Y\subseteq [n]$ is shattered if for every binary string $\vec{b}$ of length $|Y|$, ... more >>>


TR15-123 | 31st July 2015
Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Addition is exponentially harder than counting for shallow monotone circuits

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>




ISSN 1433-8092 | Imprint