Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xi Chen:

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