Xi Chen 0001

SODA Conference 2025 Conference Paper

Lower Bounds for Convexity Testing

• Xi Chen 0001
• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio
• Erik Waingarten

STOC Conference 2025 Conference Paper

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

• Deeparnab Chakrabarty
• Xi Chen 0001
• Simeon Ristic
• C. Seshadhri 0001
• Erik Waingarten

We study monotonicity testing of high-dimensional distributions on {−1,1} n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio and Bhattacharyya and Chakraborty. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee). We show that the subcube query complexity is Θ( n /є 2 ), by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra to real-valued functions on {−1,1} n . We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio, using subcube conditioning. We show that the query complexity is Θ(√ n /є 2 ). Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.

SODA Conference 2025 Conference Paper

Relative-error monotonicity testing

• Xi Chen 0001
• Anindya De
• Yizhi Huang
• Yuhao Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio
• Tianqi Yang

STOC Conference 2024 Conference Paper

Computing a Fixed Point of Contraction Maps in Polynomial Queries

• Xi Chen 0001
• Yuhao Li 0002
• Mihalis Yannakakis

STOC Conference 2024 Conference Paper

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

• Xi Chen 0001
• Yumou Fei
• Shyamal Patel

We give a distribution-free testing algorithm for decision lists with Õ( n 11/12 /ε 3 ) queries. This is the first sublinear algorithm for this problem, which shows that, unlike halfspaces, testing is strictly easier than learning for decision lists. Complementing the algorithm, we show that any distribution-free tester for decision lists must make Ω(√ n ) queries, or draw Ω( n ) samples when the algorithm is sample-based.

SODA Conference 2024 Conference Paper

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas

• Xi Chen 0001
• Anindya De
• Yuhao Li 0002
• Shivam Nadimpalli
• Rocco A. Servedio

SODA Conference 2024 Conference Paper

Smoothed Complexity of SWAP in Local Graph Partitioning

• Xi Chen 0001
• Chenghao Guo
• Emmanouil V. Vlatakis-Gkaragkounis
• Mihalis Yannakakis

SODA Conference 2024 Conference Paper

Uniformity Testing over Hypergrids with Subcube Conditioning

• Xi Chen 0001
• Cassandra Marcussen

We give an algorithm for testing uniformity of distributions supported on hypergrids [ m 1 ] × · · · × [ m n ], which makes many queries to a subcube conditional sampling oracle with m = max i m i. When m is a constant, our algorithm is nearly optimal and strengthens the algorithm of Canonne et al. (SODA 2021) which has the same query complexity but works for hypercubes {±1} n only. A key technical contribution behind the analysis of our algorithm is a proof of a robust version of Pisier's inequality for functions over hypergrids using Fourier analysis.

SODA Conference 2023 Conference Paper

Approximate Trace Reconstruction from a Single Trace

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

The well-known trace reconstruction problem is the problem of inferring an unknown source string x ∈ {0, 1} n from independent “traces”, i. e. copies of x that have been corrupted by a δ-deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. The current paper considers the extreme data-limited regime in which only a single trace is provided to the reconstruction algorithm. In this setting exact reconstruction is of course impossible, and the question is to what accuracy the source string x can be approximately reconstructed. We give a detailed study of this question, providing algorithms and lower bounds for the high, intermediate, and low deletion rate regimes in both the worst-case ( x is arbitrary) and average-case ( x is drawn uniformly from {0, 1} n ) models. In several cases the lower bounds we establish are matched by computationally efficient algorithms that we provide. We highlight our results for the high deletion rate regime: roughly speaking, they show that • Having access to a single trace is already quite useful for worst-case trace reconstruction: an efficient algorithm can perform much more accurate reconstruction, given one trace that is even only a few bits long, than it could given no traces at all. But in contrast • in the average-case setting, having access to a single trace is provably not very useful: no algorithm, computationally efficient or otherwise, can achieve significantly higher accuracy given one trace that is o ( n ) bits long than it could with no traces. * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 03292

STOC Conference 2023 Conference Paper

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules

• Xi Chen 0001
• Binghui Peng

We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.

STOC Conference 2023 Conference Paper

Streaming Euclidean MST to a Constant Factor

• Xi Chen 0001
• Vincent Cohen-Addad
• Rajesh Jayaram
• Amit Levi
• Erik Waingarten

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n -point set X ⊂ ℝ d . In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+є) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG ’05]. However, for high dimensional spaces the best known approximation for this problem was Õ(log n ), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O (log 2 n ) bound due to [Indyk, STOC ’04] and [Andoni, Indyk, Krauthgamer, SODA ’08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any є≥ 1, our algorithm achieves an Õ(є −2 ) approximation in n O (є) space. We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Ω(√ n ) space, demonstrating that (1+є) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+є) approximations are possible in sublinear space with O (1/є) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+ O (logα + 1/ α є)) approximation in n O (є) d O (1) space. All our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+є)-approximation to Euclidean MST in a constant number of rounds in the MPC model. Previously, such a result was only known for low-dimensional space [Andoni, Nikolov, Onak, Yaroslavtsev, STOC ’15], or required either O (log n ) rounds or a O (log n ) approximation.

SODA Conference 2022 Conference Paper

Average-Case Subset Balancing Problems

• Xi Chen 0001
• Yaonan Jin
• Tim Randolph 0001
• Rocco A. Servedio

Given a set of n input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time O ∗(3 0. 387 n ) in the average case, significantly improving over the O ∗(3 0. 488 n ) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O ∗(3 0. 5 n ). Our algorithm generalizes to a number of related problems, such as the “Generalized Equal Subset Sum” problem, which asks us to assign a coefficient c i from a set C to each input number x i such that Σ i c i x i = 0. Our algorithm for the average-case version of this problem runs in time for some positive constant c 0, whenever C = {0, ± 1, …, ± d} or {±1, …, ± d } for some positive integer d (with runtime O ∗( |C| 0. 45 n ) when |C| < 10). Our results extend to the problem of finding “nearly balanced” solutions in which the target is a not-too-large nonzero offset τ. Our approach relies on new structural results that characterize the probability that Σ i c i x i = τ has a solution c ∊ C n when x i 's are chosen randomly; these results may be of independent interest. Our algorithm is inspired by the “representation technique” introduced by Howgrave-Graham and Joux [HGJ10]. This requires several new ideas to overcome preprocessing hurdles that arise in the representation framework, as well as a novel application of dynamic programming in the solution recovery phase of the algorithm.

SODA Conference 2022 Conference Paper

Computational Hardness of the Hylland-Zeckhauser Scheme

• Thomas Chen
• Xi Chen 0001
• Binghui Peng
• Mihalis Yannakakis

We study the complexity of the classic Hylland-Zeckhauser scheme [21] for one-sided matching markets. We show that the problem of finding an ∊ -approximate equilibrium in the HZ scheme is PPAD-hard, and this holds even when ∊ is polynomially small and when each agent has no more than four distinct utility values. Our hardness result, when combined with the PPAD membership result of [29], resolves the approximation complexity of the HZ scheme. We also show that the problem of approximating within a certain constant factor the optimal social welfare (the weight of the matching) achievable by HZ equilibria is NP-hard.

FOCS Conference 2022 Conference Paper

Memory Bounds for Continual Learning

• Xi Chen 0001
• Christos H. Papadimitriou
• Binghui Peng

Continual learning, or lifelong learning, is a formidable current challenge to machine learning. It requires the learner to solve a sequence of k different learning tasks, one after the other, while retaining its aptitude for earlier tasks; the continual learner should scale better than the obvious solution of developing and maintaining a separate learner for each of the k tasks. We embark on a complexity-theoretic study of continual learning in the PAC framework. We make novel uses of communication complexity to establish that any continual learner, even an improper one, needs memory that grows linearly with k, strongly suggesting that the problem is intractable. When logarithmically many passes over the learning tasks are allowed, we provide an algorithm based on multiplicative weights update whose memory requirement scales well; we also establish that improper learning is necessary for such performance. We conjecture that these results may lead to new promising approaches to continual learning.

SODA Conference 2022 Conference Paper

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

In the standard trace reconstruction problem, the goal is to exactly reconstruct an unknown source string x ∊ {0, 1} n from independent “traces”, which are copies of x that have been corrupted by a δ -deletion channel which independently deletes each bit of x with probability δ and concatenates the surviving bits. We study the approximate trace reconstruction problem, in which the goal is only to obtain a high-accuracy approximation of x rather than an exact reconstruction. We give an efficient algorithm, and a near-matching lower bound, for approximate reconstruction of a random source string x ∊ {0, 1} n from few traces. Our main algorithmic result is a polynomial-time algorithm with the following property: for any deletion rate 0 < δ < 1 (which may depend on n ), for almost every source string x ∊ {0, 1} n, given any number M ≤ Θ(1/ δ ) of traces from Del δ (x), the algorithm constructs a hypothesis string that has edit distance at most n · ( δM ) Ω ( M ) from x. We also prove a near-matching information-theoretic lower bound showing that given M ≤ Θ(1/ δ ) traces from Del δ (x) for a random n -bit string x, the smallest possible expected edit distance that any algorithm can achieve, regardless of its running time, is n · ( δM ) O (M).

STOC Conference 2022 Conference Paper

New streaming algorithms for high dimensional EMD and MST

• Xi Chen 0001
• Rajesh Jayaram
• Amit Levi
• Erik Waingarten

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an n -point set X ⊂ {1,2,…,Δ} d , and computing the Earth Mover Distance (EMD) between two multi-sets A , B ⊂ {1,2,…,Δ} d of size n . We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of Õ(log n ) and using ( n , d ,Δ)-space only. Furthermore, our algorithm for EMD can be compressed to a single pass with a small additive error. Previously, the best known sublinear-space streaming algorithms for either problem achieved an approximation of O (min{ log n , log(Δ d )} log n ). For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of Ω(log n ), analogous to the Ω(log n ) lower bound for EMD.

STOC Conference 2022 Conference Paper

On the complexity of dynamic submodular maximization

• Xi Chen 0001
• Binghui Peng

We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of n insertions and deletions. We show that any algorithm that maintains a (0.5+є)-approximate solution under a cardinality constraint, for any constant є>0, must have an amortized query complexity that is polynomial in n . Moreover, a linear amortized query complexity is needed in order to maintain a 0.584-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMN+20, Mon20] that achieve (0.5−є)-approximation with a polylog ( n ) amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee 1−1/ e −є and amortized query complexities O (log( k /є)/є 2 ) and k Õ(1/є 2 ) log n , respectively, where k denotes the cardinality parameter or the rank of the matroid.

SODA Conference 2021 Conference Paper

Polynomial-time trace reconstruction in the smoothed complexity model

• Xi Chen 0001
• Anindya De
• Chin Ho Lee
• Rocco A. Servedio
• Sandip Sinha

In the trace reconstruction problem, an unknown source string x ∊ {0, 1} n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in {0, 1} n [6, 19, 7, 8, 4] and in the average-case setting where x is drawn uniformly at random from {0, 1} n [21, 9, 8, 4]. This paper studies trace reconstruction in the smoothed analysis setting, in which a “worst-case” string x worst is chosen arbitrarily from {0, 1} n, and then a perturbed version x of x worst is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct x given independent traces from it. Our main result is an algorithm which, for any constant perturbation rate 0 < σ < 1 and any constant deletion rate 0 < δ < 1, uses poly( n ) running time and traces and succeeds with high probability in reconstructing the string x. This stands in contrast with the worst-case version of the problem, for which the best known sample complexity is exp( Õ ( n 1/5 )) [5], a recent improvement on exp( O ( n 1/3 )) [6, 19]. Our approach is based on reconstructing x from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly( n )-time procedure for reconstructing the multiset of all O (log n )-length subwords of any source string x ∊ {0, 1} n given access to traces of x.

SODA Conference 2021 Conference Paper

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

• Clément L. Canonne
• Xi Chen 0001
• Gautam Kamath 0001
• Amit Levi
• Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on {–1, 1} n, which makes many queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restrictions for distributions on {–1, 1} n, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

SODA Conference 2020 Conference Paper

A Lower Bound on Cycle-Finding in Sparse Digraphs

• Xi Chen 0001
• Tim Randolph 0001
• Rocco A. Servedio
• Timothy Sun

SODA Conference 2020 Conference Paper

Nearly optimal edge estimation with independent set queries

• Xi Chen 0001
• Amit Levi
• Erik Waingarten

We study the problem of estimating the number of edges of an unknown, undirected graph G = ([ n ], E ) with access to an independent set oracle. When queried about a subset S ⊆ [ n ] of vertices, the independent set oracle answers whether S is an independent set in G or not. Our first main result is an algorithm that computes a (1 + ϵ )-approximation of the number of edges m of the graph using · poly(log n, 1/ ϵ ) independent set queries. This improves the upper bound of · poly(log n, 1/ ε ) by Beame et al. [3]. Our second main result shows that /polylog( n ) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of poly(log n, 1/ ϵ ).

STOC Conference 2020 Conference Paper

Smoothed complexity of local max-cut and binary max-CSP

• Xi Chen 0001
• Chenghao Guo
• Emmanouil V. Vlatakis-Gkaragkounis
• Mihalis Yannakakis
• Xinzhi Zhang 0002

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φ n O (√log n ) , where n is the number of nodes in the graph and φ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of φ n O (log n ) by Etscheid and Roglin. Our result is based on an analysis of long sequences of flips, which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems.

FOCS Conference 2019 Conference Paper

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel

• Frank Ban
• Xi Chen 0001
• Adam Freilich
• Rocco A. Servedio
• Sandip Sinha

Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the bit-flip noise channel and for the erasure noise channel. In this paper we initiate the study of population recovery under the deletion channel, in which each bit b is independently deleted with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the trace reconstruction problem, which is a challenging problem that has received much recent attention. In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value ℓ > 1. As our main sample complexity upper bound, we show that for any population size ℓ = o(log n / log log n), a population of ℓ strings from {o, 1} n can be learned under deletion channel noise using 2 n(1/2+o(1)) samples. On the lower bound side, we show that at least n Ω(ℓ) samples are required to perform population recovery under the deletion channel when the population size is ℓ, for all ℓ ≤ n 1/2-ε. Our upper bounds are obtained via a robust multivariate generalization of a polynomial-based analysis, due to Krasikov and Roddity [KR97], of how the k-deck of a bit-string uniquely identifies the string; this is a very different approach from recent algorithms for trace reconstruction (the ℓ = 1 case). Our lower bounds build on moment-matching results of Roos[Roos: 00] and Daskalakis and Papadimitriou[DP15].

STOC Conference 2019 Conference Paper

Testing unateness nearly optimally

• Xi Chen 0001
• Erik Waingarten

We present an Õ( n 2/3 /є 2 )-query algorithm that tests whether an unknown Boolean function f ∶{0,1} n → {0,1} is unate (i.e., every variable is either non-decreasing or non-increasing) or є-far from unate. The upper bound is nearly optimal given the Ω( n 2/3 ) lower bound of Chen, Waingarten and Xie (2017). The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.

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.

SODA Conference 2018 Conference Paper

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer

• Xi Chen 0001
• George Matikas
• Dimitris Paparas
• Mihalis Yannakakis

We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand bundle at its given price or any subset of items at their total individual prices. The following problems are also #P-hard, as immediate corollaries of the proof: 1. determining if individual item pricing is optimal for a given instance, 2. determining if grand bundle pricing is optimal, and 3. computing the optimal (deterministic) revenue. On the positive side, we show that when the distributions are i. i. d. with support size 2, the optimal revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore, it can be computed in polynomial time. The problem can be solved in polynomial time too when the number of items is constant.

STOC Conference 2017 Conference Paper

Addition is exponentially harder than counting for shallow monotone circuits

• Xi Chen 0001
• Igor C. Oliveira 0001
• Rocco A. Servedio

Let Add k , N denote the Boolean function which takes as input k strings of N bits each, representing k numbers a (1) ,…, a ( k ) in {0,1,…,2 N -1}, and outputs 1 if and only if a (1) + … + a ( k ) ≥ 2 N . Let MAJ t , n denote a monotone unweighted threshold gate , i.e., the Boolean function which takes as input a single string x Ε {0,1} n and outputs 1 if and only if x 1 + … + x n ≥ t . The function Add k , N may be viewed as a monotone function that performs addition, and MAJ t , n may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as monotone majority circuits. The main result of this paper is an exponential lower bound on the size of bounded-depth monotone majority circuits that compute Add k , N . More precisely, we show that for any constant d ≥ 2, any depth- d monotone majority circuit that computes Add d , N must have size 2 Ω( N 1/ d ) . As Add k , N can be computed by a single monotone weighted threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth monotone majority circuits require exponential size to simulate monotone weighted threshold gates. This answers a question posed by Goldmann and Karpinski (STOC'93) and recently restated by Hastad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth- d , size 2 O ( N 1/ d ) monotone majority circuit for Add d , N . As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM'87). They exhibited a monotone function that is in AC 0 but requires super-polynomial size for any constant-depth monotone circuit composed of unbounded fan-in AND and OR gates. We describe a monotone function that is in depth-3 AC 0 but requires exponential size monotone circuits of any constant depth, even if the circuits are composed of MAJ gates.

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).

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.

STOC Conference 2016 Conference Paper

Near-optimal small-depth lower bounds for small distance connectivity

• Xi Chen 0001
• Igor C. Oliveira 0001
• Rocco A. Servedio
• Li-Yang Tan

We show that any depth- d circuit for determining whether an n -node graph has an s -to- t path of length at most k must have size n Ω( k 1/ d / d ) when k ( n ) ≤ n 1/5 , and n Ω( k 1/5 d / d ) when k ( n )≤ n . The previous best circuit size lower bounds were n k exp(− O ( d )) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and n Ω((log k )/ d ) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth- d circuits of size n O ( k 2/ d ) for this problem (and strengthening our bound even to n k Ω(1/ d ) would require proving that undirected connectivity is not in NC 1 ). Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections , an extension of random restrictions which were recently employed by Rossman, Servedio, and Tan (FOCS 2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.

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.

STOC Conference 2015 Conference Paper

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

• Xi Chen 0001
• Anindya De
• Rocco A. Servedio
• Li-Yang Tan

We prove a lower bound of Ω(n 1/2-c ), for all c> 0, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an n-variable Boolean function is monotone versus constant-far from monotone. This improves a ~Ω(n 1/5 ) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n 1/2 /ε 2 ) by Khot et al. [13].

STOC Conference 2015 Conference Paper

On the Complexity of Nash Equilibria in Anonymous Games

• Xi Chen 0001
• David Durfee
• Anthi Orfanou

We show that the problem of finding an ε-approximate Nash equilibrium in an {anonymous} game with seven pure strategies is complete in PPAD, when the approximation parameter ε is exponentially small in the number of players.

FOCS Conference 2015 Conference Paper

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

• Xi Chen 0001
• Ilias Diakonikolas
• Anthi Orfanou
• Dimitris Paparas
• Xiaorui Sun
• Mihalis Yannakakis

We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, PNP = P#P), there is no universal efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.

FOCS Conference 2014 Conference Paper

New Algorithms and Lower Bounds for Monotonicity Testing

• Xi Chen 0001
• Rocco A. Servedio
• Li-Yang Tan

We consider the problem of testing whether an unknown Boolean function f: {- 1, 1} n → {-1, 1} is monotone versus ε-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an Ω̅(n 1/5 ) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function f is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of Ω(log n) due to Fischer et al. [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains {1, ···, m} n for all m ≥ 2. Upper bound: We present an O(n 5/6 ) poly(1/ε)-query algorithm that tests whether an unknown Boolean function f is monotone versus ε-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri[2], which makes O(n 7/8 ) poly(1/ε) queries.

SODA Conference 2014 Conference Paper

The Complexity of Optimal Multidimensional Pricing

• Xi Chen 0001
• Ilias Diakonikolas
• Dimitris Paparas
• Xiaorui Sun
• Mihalis Yannakakis

We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i. e. , the optimal item pricing problem, when the buyer's values for the items are independent. We show that the problem of computing a revenue-optimal pricing can be solved in polynomial time for distributions of support size 2 and its decision version is NP-complete for distributions of support size 3. We also show that the problem remains NP-complete for the case of identical distributions.

FOCS Conference 2013 Conference Paper

Faster Canonical Forms for Strongly Regular Graphs

• László Babai
• Xi Chen 0001
• Xiaorui Sun
• Shang-Hua Teng
• John Wilmes

We show that a canonical form for strongly regular (s. r.) graphs can be found in time exp(O~(n1/5)) and therefore isomorphism of s. r. graphs can be tested within the same time bound, where n is the number of vertices and the tilde hides a polylogarithmic factor. The best previous bound for testing isomorphism of s. r. graphs was exp(O~(n1/3)) (Spiel man, STOC 1996) while the bound for GI in general has been standing firmly at exp(O~(n1/2)) for three decades. (These results, too, provided canonical forms.) The previous bounds on isomorphism of s. r. graphs (Babai 1980 and Spiel man 1996) were based on the analysis of the classical individualization/refinement (I/R) heuristic. The present bound depends on a combination of a deeper analysis of the I/R heuristic with Luks's group theoretic divide-and-conquer methods following Babai-Luks (STOC 1983) and Miller (1983). Our analysis builds on Spiel man's work that brought Neumaier's 1979 classification of s. r. graphs to bear on the problem. One of Neumaier's classes, the line-graphs of Steiner 2-designs, has been eliminated as a bottleneck in recent work by the present authors (STOC'13). In the remaining hard cases, we have the benefit of Neumaier's claw bound" and its asymptotic consequences derived by Spiel man, some of which we improve via a new "clique geometry. " We also prove, by an analysis of the I/R heuristic, that, with known (trivial) exceptions, s. r. graphs have exp(O~(n9/37)) automorphisms, improving Spiel man's exp(O~(n1/3)) bound. No knowledge of group theory is required for this paper. The group theoretic method is only used through an easily stated combinatorial consequence (Babai -- Luks, 1983 combined with Miller, 1983). While the bulk of this paper is joint work by the five authors, it also includes two contributions by subsets of the authors: the clique geometry [BW] and the auto orphism bound [CST]. "

STOC Conference 2013 Conference Paper

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems

• Xi Chen 0001
• Xiaorui Sun
• Shang-Hua Teng

A standard heuristic for testing graph isomorphism is to first assign distinct labels to a small set of vertices of an input graph, and then propagate to create new vertex labels across the graph, aiming to assign distinct and isomorphism-invariant labels to all vertices in the graph. This is usually referred to as the individualization/refinement method for canonical labeling of graphs. We present a quasipolynomial-time algorithm for isomorphism testing of Steiner 2-systems. A Steiner 2-system consists of points and lines, where each line passes the same number of points and each pair of points uniquely determines a line. Each Steiner 2-system induces a Steiner graph, in which vertices represent lines and edges represent intersections of lines. Steiner graphs are an important subfamily of strongly regular graphs whose isomorphism testing has challenged researchers for years. Inspired by both the individualization/refinement method and the previous analyses of Babai and Spielman, we consider an extended framework for isomorphism testing of Steiner 2-systems, in which we use a small set of randomly chosen points and lines to build isomorphism-invariant multi-stage combinatorial structures that are sufficient to distinguish all pairs of points of a Steiner 2-system. Applying this framework, we show that isomorphism of Steiner 2-systems with n lines can be tested in time smash{n O(log n) }, improving the previous best bound of smash{exp(~{O}(n 1/4 ))} by Spielman. Before our result, quasipolynomial-time isomorphism testing was only known for the case when the line size is polylogarithmic, as shown by Babai and Luks. A result essentially identical to ours was obtained simultaneously by Laszlo Babai and John Wilmes. They performed a direct analysis of the individualization/refinement method, building on a different philosophy and combinatorial structure theory. We comment on how this paper fits into the overall project of improved isomorphism testing for strongly regular graphs (the ultimate goal being subexponential exp(n o(1) ) time). In the remaining cases, we only need to deal with strongly regular graphs satisfying "Neumaier's claw bound," permitting the use of a separate set of asymptotic structural tools. In joint work (in progress) with Babai and Wilmes, we address that case and have already pushed the overall bound below smash{exp(~{O}(n 1/4 ))}. The present paper is a methodologically distinct and stand-alone part of the overall project.

STOC Conference 2013 Conference Paper

The complexity of non-monotone markets

• Xi Chen 0001
• Dimitris Paparas
• Mihalis Yannakakis

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We show that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utilities, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter, ρ, is any constant less than -1.

STOC Conference 2012 Conference Paper

Complexity of counting CSP with complex weights

• Jin-Yi Cai
• Xi Chen 0001

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions. We show that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not-necessarily-symmetric binary function; and (c) the unweighted form of #CSP is when all functions in F take values in {0,1}.

FOCS Conference 2010 Conference Paper

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

• Jin-Yi Cai
• Xi Chen 0001

The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function Z A (G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

STOC Conference 2010 Conference Paper

How to compress interactive communication

• Boaz Barak
• Mark Braverman
• Xi Chen 0001
• Anup Rao 0001

We describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~O(√CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~O(I) bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. For average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. If μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of n evaluations of f, and obtain results analogous to those above.

FOCS Conference 2009 Conference Paper

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

• Xi Chen 0001
• Decheng Dai
• Ye Du
• Shang-Hua Teng

We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme, unless every problem in PPAD is solvable in polynomial time.

STOC Conference 2008 Conference Paper

A quadratic lower bound for the permanent and determinant problem over any characteristic! = 2

• Jin-Yi Cai
• Xi Chen 0001
• Dong Li

In Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field F of characteristic ≠2, and an integer n, what is the minimum m such that the permanent of an n x n matrix X=(x ij ) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of x ij 's, and the equality is in F [X]. Mignon and Ressayre (2004) [11] proved a quadratic lower bound m=Ω(n 2 ) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠2.

FOCS Conference 2007 Conference Paper

Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation

• Xi Chen 0001
• Shang-Hua Teng

In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1: n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1: n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1: n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1: n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).

SODA Conference 2007 Conference Paper

The approximation complexity of win-lose games

• Xi Chen 0001
• Shang-Hua Teng
• Paul Valiant

FOCS Conference 2006 Conference Paper

Computing Nash Equilibria: Approximation and Smoothed Complexity

• Xi Chen 0001
• Xiaotie Deng
• Shang-Hua Teng

We advance significantly beyond the recent progress on the algorithmic complexity of Nash equilibria by solving two major open problems in the approximation of Nash equilibria and in the smoothed analysis of algorithms. --We show that no algorithm with complexity poly(n, \frac{1} { \in } ) can compute an \in-approximate Nash equilibrium in a two-player game, in which each player has n pure strategies, unless PPAD \subseteq P. In other words, the problem of computing a Nash equilibrium in a twoplayer game does not have a fully polynomial-time approximation scheme unless PPAD \subseteq P. --We prove that no algorithm for computing a Nash equilibrium in a two-player game can have smoothed complexity poly(n, \frac{1} {\sigma } ) under input perturbation of magnitude s, unless PPAD \subseteq RP. In particular, the smoothed complexity of the classic Lemke-Howson algorithm is not polynomial unless PPAD \subseteq RP. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional hypergrid with constant side-length, and show that it can host the embedding of the proof structure of any PPAD problem. We prove a key geometric lemma for finding a discrete fixed-point, a new concept defined on n + 1 vertices of a unit hypercube. This lemma enables us to overcome the curse of dimensionality in reasoning about fixed-points in high dimensions.

FOCS Conference 2006 Conference Paper

Settling the Complexity of Two-Player Nash Equilibrium

• Xi Chen 0001
• Xiaotie Deng

We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete.

STOC Conference 2005 Conference Paper

On algorithms for discrete and approximate brouwer fixed points

• Xi Chen 0001
• Xiaotie Deng

We study the algorithmic complexity of the discrete fixed point problem and develop an asymptotic matching bound for a cube in any constantly bounded finite dimension. To obtain our upper bound, we derive a new fixed point theorem, based on a novel characterization of boundary conditions for the existence of fixed points.In addition, exploring a linkage with the approximation problem of the continuous fixed point problem, we obtain asymptotic matching bounds for complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions that close a previous exponential gap. It settles a fifteen years old open problem of Hirsch, Papadimitriou and Vavasis by improving both the upper and lower bounds.Our new characterization for existence of a fixed point is also applicable to functions defined on non-convex domain and makes it a potentially useful tool for design and analysis of algorithms for fixed points in general domain.