The relative-error property testing model was introduced in [Chen et al., 2024] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only a small fraction of all input assignments satisfy the function. In this framework, the distance from the unknown target function f that is being tested to a function g is defined as Vol(f△g)/Vol(f), where the numerator is the fraction of inputs on which f and g disagree and the denominator is the fraction of inputs that satisfy f. Recent work [Chen et al., 2026] has shown that over the Boolean domain {0,1}ⁿ, any relative-error testing algorithm for the fundamental class of {halfspaces} (i.e. linear threshold functions) must make Ω(log n) oracle calls. In this paper we complement the [Chen et al., 2026] lower bound by showing that halfspaces can be relative-error tested over ℝⁿ under the standard N(0,I_n) Gaussian distribution using a sublinear number of oracle calls - in particular, substantially fewer than would be required for learning. Our results use a wide range of tools including Hermite analysis, Gaussian isoperimetric inequalities, and geometric results on noise sensitivity and surface area.

The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [X. Chen et al., 2025; Chen et al., 2025; Chen et al., 2025]. In this paper we consider the problem of relative-error testing an unknown and arbitrary f: {0,1}ⁿ → {0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the n input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes Õ(log(N)/ε) samples and queries, where N = |f^{-1}(1)| is the number of satisfying assignments of the function that is being tested and the value of N is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of N and with high probability makes Õ(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of N up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.

The Graph Reconstruction Conjecture famously posits that any undirected graph on at least three vertices is determined up to isomorphism by its family of (unlabeled) induced subgraphs. At present, the conjecture admits partial resolutions of two types: 1) casework-based demonstrations of reconstructibility for families of graphs satisfying certain structural properties, and 2) probabilistic arguments establishing reconstructibility of random graphs by leveraging average-case phenomena. While results in the first category capture the worst-case nature of the conjecture, they play a limited role in understanding the general case. Results in the second category address much larger graph families, but it remains unclear how heavily the necessary arguments rely on optimistic distributional properties. Drawing on the algorithmic notions of smoothed and semi-random analysis, we study the robustness of what are arguably the two most fundamental properties in this latter line of work: asymmetry and uniqueness of subgraphs. Notably, we find that various natural semi-random graph distributions exhibit these properties asymptotically, much like their Erdős-Rényi counterparts. In particular, Bollobás [Bollob{á}s, 1990] demonstrated that almost all Erdős-Rényi random graphs G = (V, E) ∼ G(n, p) enjoy the property that their induced subgraphs on n - Θ(1) vertices are asymmetric and mutually non-isomorphic, for 1 - p, p = Ω(log(n) / n). As our primary result, we demonstrate that this property is robust against perturbation - even when an adversary is permitted to add/remove each vertex pair in V^{(2)} with (independent) arbitrarily large constant probability. Exploiting this result, we derive asymptotic characterizations of asymmetry in random graphs with large planted structure and bounded adversarial corruptions, along with improved bounds on the probability mass of nonreconstructible graphs in G(n, p).

Several recent works (Chen et al., SODA 2025; Chen et al., ICALP 2025; Chen et al., COLT 2025; Chen et al., manuscript) have studied a model of property testing of Boolean functions under a relative-error criterion. In this model, the distance from a target function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\) that is being tested to a function \(g\) is defined relative to the number of inputs \(x\) for which \(f(x) = 1\); moreover, testing algorithms in this model have access both to a black-box oracle for \(f\) and to independent uniform satisfying assignments of \(f\). The motivation for this model is that it provides a natural framework for testing sparse Boolean functions that have few satisfying assignments, analogous to well-studied models for property testing of sparse graphs.

The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems.

Abstract. We study the problem of finding a Tarski fixed point over the [Formula: see text]-dimensional grid [Formula: see text]. 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 Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.

This paper considers the junta testing problem in a recently introduced “relative error” variant of the standard Boolean function property testing model. In relative-error testing we measure the distance from $f$ to $g$, where $f,g: \{0,1\}^n \to \{0,1\}$, by the ratio of $|f^{-1}(1) \triangle g^{-1}(1)|$ (the number of inputs on which $f$ and $g$ disagree) to $|f^{-1}(1)|$ (the number of satisfying assignments of $f$), and we give the testing algorithm both black-box access to $f$ and also access to independent uniform samples from $f^{-1}(1)$. Chen et al. (SODA 2025) observed that the class of $k$-juntas is poly$(2^k,1/\epsilon)$-query testable in the relative-error model, and asked whether poly$(k,1/\epsilon)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(k/\epsilon)$-query algorithm, matching the optimal complexity achieved in the less challenging standard model. Moreover, as our main result, we show that any subclass of $k$-juntas that is closed under permuting variables is relative-error testable with a similar complexity. This gives highly efficient relative-error testing algorithms for a number of well-studied function classes, including size-$k$ decision trees, size-$k$ branching programs, and size-$k$ Boolean formulas.

A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.

We study the relative-error property testing model for Boolean functions that was recently introduced in the work of [X. Chen et al., 2025]. In relative-error testing, the testing algorithm gets uniform random satisfying assignments as well as black-box queries to f, and it must accept f with high probability whenever f has the property that is being tested and reject any f that is relative-error far from having the property. Here the relative-error distance from f to a function g is measured with respect to |f^{-1}(1)| rather than with respect to the entire domain size 2ⁿ as in the Hamming distance measure that is used in the standard model; thus, unlike the standard model, relative-error testing allows us to study the testability of sparse Boolean functions that have few satisfying assignments. It was shown in [X. Chen et al., 2025] that relative-error testing is at least as difficult as standard-model property testing, but for many natural and important Boolean function classes the precise relationship between the two notions is unknown. In this paper we consider the well-studied and fundamental properties of being a conjunction and being a decision list. In the relative-error setting, we give an efficient one-sided error tester for conjunctions with running time and query complexity O(1/ε). Secondly, we give a two-sided relative-error Õ(1/ε) tester for decision lists, matching the query complexity of the state-of-the-art algorithm in the standard model [Nader H. Bshouty, 2020; I. Diakonikolas et al., 2007].

The standard model of Boolean function property testing is not well suited for testing sparse functions which have few satisfying assignments, since every such function is close (in the usual Hamming distance metric) to the constant-0 function. In this work we propose and investigate a new model for property testing of Boolean functions, called relative-error testing, which provides a natural framework for testing sparse functions.

We consider the problem of testing whether an unknown and arbitrary set S ⊆ ℝn (given as a black-box membership oracle) is convex, versus ε-far from every convex set, under the standard Gaussian distribution.

We give an algorithm for finding an ε-fixed point of a contraction map f : [0, 1] k \(\mapsto\) [0, 1] k under the \(\ell _\infty\) -norm with query complexity O ( k log (1/ε).

In the trace reconstruction problem , an unknown source string x ∈ {0,1} n is sent through a probabilistic deletion channel that 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 [ 7 , 8 , 10 , 11 , 12 , 23 ] and in the average-case setting where x is drawn uniformly at random from {0,1} n [ 7 , 8 , 12 , 13 , 25 ]. This article 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 that, 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 \(\text{exp}(\tilde{O}(n^{1/5}))\) is the best known time and sample complexity [ 8 ]. 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 .

The goal of trace reconstruction is to reconstruct an unknown n-bit string x given only independent random traces of x, where a random trace of x is obtained by passing x through a deletion channel. A Statistical Query (SQ) algorithm for trace reconstruction is an algorithm which can only access statistical information about the distribution of random traces of x rather than individual traces themselves. Such an algorithm is said to be 𝓁-local if each of its statistical queries corresponds to an 𝓁-junta function over some block of 𝓁 consecutive bits in the trace. Since several - but not all - known algorithms for trace reconstruction fall under the local statistical query paradigm, it is interesting to understand the abilities and limitations of local SQ algorithms for trace reconstruction. In this paper we establish nearly-matching upper and lower bounds on local Statistical Query algorithms for both worst-case and average-case trace reconstruction. For the worst-case problem, we show that there is an Õ(n^{1/5})-local SQ algorithm that makes all its queries with tolerance τ ≥ 2^{-Õ(n^{1/5})}, and also that any Õ(n^{1/5})-local SQ algorithm must make some query with tolerance τ ≤ 2^{-Ω̃(n^{1/5})}. For the average-case problem, we show that there is an O(log n)-local SQ algorithm that makes all its queries with tolerance τ ≥ 1/poly(n), and also that any O(log n)-local SQ algorithm must make some query with tolerance τ ≤ 1/poly(n).

Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families. A function $f: \{0,1\}^n \to \{0,1\}$ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of $[n]$. Our main results are that -- in sharp contrast with the property of being a monotone set system -- the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: $\bullet$ For $ε\geq Ω(1/\sqrt{n})$, any non-adaptive two-sided $ε$-tester for intersectingness must make $2^{Ω(n^{1/4}/\sqrtε)}$ queries. We also give a $2^{Ω(\sqrt{n \log(1/ε)})}$-query lower bound for non-adaptive one-sided $ε$-testers for intersectingness. $\bullet$ For $ε\geq 1/2^{Ω(n^{0.49})}$, any non-adaptive two-sided $ε$-tester for union-closedness must make $n^{Ω(\log(1/ε))}$ queries. Thus, neither intersectingness nor union-closedness shares the $\mathrm{poly}(n,1/ε)$-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple $\mathrm{poly}(n^{\sqrt{n\log(1/ε)}},1/ε)$-query, one-sided, non-adaptive algorithm for $ε$-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when $ε= Θ(1/\sqrt{n})$, and for one-sided testing of intersectingness when $ε=Θ(1).$

We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a constant separation between the “yes” and “no” cases. Specifically, we give

We give the first quasipolynomial upper bound φnpolylog(n) for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width) under the full perturbation model, 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. More generally, we show that the same quasipolynomial upper bound holds for the smoothed complexity of the 2-FLIP algorithm for any binary Maximum Constraint Satisfaction Problem, including local Max-Cut, for which similar bounds were only known for 1-FLIP. Our results are based on an analysis of a new notion of useful cycles in the multigraph formed by long sequences of double flips, showing that it is unlikely for every double flip in a long sequence to incur a positive but small improvement in the cut weight.

We give an algorithm for testing uniformity of distributions supported on hypergrids [m1] × · · · × [mn], which makes many queries to a subcube conditional sampling oracle with m = maximi. 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.

We give an algorithm for finding an є-fixed point of a contraction map f:[0,1]k↦[0,1]k under the ℓ∞-norm with query complexity O (k2log(1/є ) ).

We give a distribution-free testing algorithm for decision lists with Õ(n11/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.

A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) $n$-input Subset Sum problem that runs in time $2^{(1/2 - c)n}$ for some constant $c>0$. In this paper we give a Subset Sum algorithm with worst-case running time $O(2^{n/2} \cdot n^{-γ})$ for a constant $γ> 0.5023$ in standard word RAM or circuit RAM models. To the best of our knowledge, this is the first improvement on the classical ``meet-in-the-middle'' algorithm for worst-case Subset Sum, due to Horowitz and Sahni, which can be implemented in time $O(2^{n/2})$ in these memory models. Our algorithm combines a number of different techniques, including the ``representation method'' introduced by Howgrave-Graham and Joux and subsequent adaptations of the method in Austrin, Kaski, Koivisto, and Nederlof, and Nederlof and Wegrzycki, and ``bit-packing'' techniques used in the work of Baran, Demaine, and Patrascu on subquadratic algorithms for 3SUM.

We prove a $k^{-\Omega\left(\log \left(\varepsilon_{2}-\varepsilon_{1}\right)\right)}$ lower bound for adap- tively testing whether a Boolean function is $\varepsilon_{1}$-close to or $\varepsilon_{2}-$ far from k-juntas. Our results provide the first superpolynomial separation between tolerant and non-tolerant testing for a natural property of boolean functions under the adaptive setting. Furthermore, our techniques generalize to show that adaptively testing whether a function is $\varepsilon_{1}$-close to a k-junta or $\varepsilon_{2}$-far from $(k+o(k))$-juntas cannot be done with poly $(k,\left(\varepsilon_{2}-\varepsilon_{1}\right)^{-1})$ queries. This is in contrast to an algorithm by Iyer, Tal and Whitmeyer [CCC 2021] which uses poly $(k,\left(\varepsilon_{2}-\varepsilon_{1}\right)^{-1})$ queries to test whether a function is $\varepsilon_{1}$-close to a k-junta or $\varepsilon_{2}$-far from $O(k /\left(\varepsilon_{2}-\varepsilon_{1}\right)^{2})$-juntas

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 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 Õ(logn), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O(log2 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 nO(є) space.

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.

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.

We study the query complexity of finding a Tarski fixed point over the k-dimensional grid {1,...,n}k. Improving on the previous best upper bound of O(log⌈2k/3⌉n)[7], we give a new algorithm with query complexity O(log⌈(k+1)/2⌉n). This is based on a novel decomposition theorem about a weaker variant of the Tarski fixed point problem, where the input consists of a monotone function f:[n]k→[n]k and a monotone sign function b:[n]k→ {-1,0,1} and the goal is to find a point x ∈ [n]k that satisfies either f(x) ≼ x and b(x) ≤ 0 or f(x) ≽ x and b(x) ≥ 0.

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.

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

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∗(30.387n) in the average case, significantly improving over the O∗(30.488n) running time of the best known worst-case algorithm [MNPW19] and the Meet-in-the-Middle benchmark of O∗(30.5n). Our algorithm generalizes to a number of related problems, such as the “Generalized Equal Subset Sum” problem, which asks us to assign a coefficient ci from a set C to each input number xi such that Σi cixi = 0. Our algorithm for the average-case version of this problem runs in time for some positive constant c0, whenever C = {0, ± 1, …, ± d} or {±1, …,±d} for some positive integer d (with runtime O∗(|C|0.45n) 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 cixi = τ has a solution c ∊ Cn when xi'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.

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 Õ(logn) 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{ logn , log(Δ d)} logn). For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of Ω(logn), analogous to the Ω(logn) lower bound for EMD.

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.

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, ${P}^{{NP}}={P}^{{\#P}}$), there is no efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.

We consider the problem of finding a cycle in a sparse directed graph G that is promised to be far from acyclic, meaning that the smallest feedback arc set , i.e., a subset of edges whose deletion results in an acyclic graph, in G is large. We prove an information-theoretic lower bound, showing that for N -vertex graphs with constant outdegree, any algorithm for this problem must make Ω̄(N 5/9 ) queries to an adjacency list representation of G . In the language of property testing, our result is an Ω̄(N 5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the Ω (√ N ) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument.

We study the problems of learning and testing junta distributions on $\{-1,1\}^n$ with respect to the uniform distribution, where a distribution $p$ is a $k$-junta if its probability mass function $p(x)$ depends on a subset of at most $k$ variables. The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning (Bhattacharyya et al 2018., Canonne et al. 2019). We give two applications: An algorithm for learning $k$-junta distributions with $\tilde{O}(k/\epsilon^2) \log n + O(2^k/\epsilon^2)$ subcube conditioning queries, and an algorithm for testing $k$-junta distributions with $\tilde{O}((k + \sqrt{n})/\epsilon^2)$ subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour et al. 2016.

In the \emph{trace reconstruction problem}, an unknown source string $x \in \{0,1\}^n$ is transmitted through a probabilistic \emph{deletion channel} which independently deletes each bit with some fixed probability $δ$ and concatenates the surviving bits, resulting in a \emph{trace} of $x$. The problem is to reconstruct $x$ given access to independent traces. Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for poly$(n)$-time algorithms being the 2004 algorithm of Batu et al. \cite{BKKM04}. This algorithm can reconstruct an arbitrary source string $x \in \{0,1\}^n$ in poly$(n)$ time provided that the deletion rate $δ$ satisfies $δ\leq n^{-(1/2 + \varepsilon)}$ for some $\varepsilon > 0$. In this work we improve on the result of \cite{BKKM04} by giving a poly$(n)$-time algorithm for trace reconstruction for any deletion rate $δ\leq n^{-(1/3 + \varepsilon)}$. Our algorithm works by alternating an alignment-based procedure, which we show effectively reconstructs portions of the source string that are not "highly repetitive", with a novel procedure that efficiently determines the length of highly repetitive subwords of the source string.

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a multiplier between 0 and 1, and her bid on each item is multiplicatively scaled down by the multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is the pacing equilibrium.

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.

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 xworst is chosen arbitrarily from {0, 1}n, and then a perturbed version x of xworst 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(Õ(n1/5)) [5], a recent improvement on exp(O(n1/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.

We consider the setting where players run the Hedge algorithm or its optimistic variant \cite{syrgkanis2015fast} to play an n-action game repeatedly for T rounds. 1) For two-player games, we show that the regret of optimistic Hedge decays at \tilde{O}( 1/T ^{5/6} ), improving the previous bound O(1/T^{3/4}) by \cite{syrgkanis2015fast}. 2) In contrast, we show that the convergence rate of vanilla Hedge is no better than \tilde{\Omega}(1/ \sqrt{T})}, addressing an open question posted in \cite{syrgkanis2015fast}. For general m-player games, we show that the swap regret of each player decays at rate \tilde{O}(m^{1/2} (n/T)^{3/4}) when they combine optimistic Hedge with the classical external-to-internal reduction of Blum and Mansour \cite{blum2007external}. The algorithm can also be modified to achieve the same rate against itself and a rate of \tilde{O}(\sqrt{n/T}) against adversaries. Via standard connections, our upper bounds also imply faster convergence to coarse correlated equilibria in two-player games and to correlated equilibria in multiplayer games.

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

We consider the problem of finding a cycle in a sparse directed graph G that is promised to be far from acyclic, meaning that the smallest feedback arc set in G is large. We prove an information-theoretic lower bound, showing that for N-vertex graphs with constant outdegree any algorithm for this problem must make (N5/9) queries to an adjacency list representation of G. In the language of property testing, our result is an (N5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the lower bound, implicit in Bender and Ron [BR02], which follows from a simple birthday paradox argument.

We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most φ n O(√logn), 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(logn) 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.

Proof-of-work blockchains reward each miner for one completed block by an amount that is, in expectation, proportional to the number of hashes the miner contributed to the mining of the block. Is this proportional allocation rule optimal? And in what sense? And what other rules are possible? In particular, what are the desirable properties that any "good" allocation rule should satisfy? To answer these questions, we embark on an axiomatic theory of incentives in proof-of-work blockchains at the time scale of a single block. We consider desirable properties of allocation rules including: symmetry; budget balance (weak or strong); sybil-proofness; and various grades of collusion-proofness. We show that Bitcoin's proportional allocation rule is the unique allocation rule satisfying a certain system of properties, but this does not hold for slightly weaker sets of properties, or when the miners are not risk-neutral. We also point out that a rich class of allocation rules can be approximately implemented in a proof-of-work blockchain.

A number of recent works have considered the trace reconstruction problem, in which an unknown source string x in {0,1}^n is transmitted through a probabilistic channel which may randomly delete coordinates or insert random bits, resulting in a trace of x. The goal is to reconstruct the original string x from independent traces of x. While the asymptotically best algorithms known for worst-case strings use exp(O(n^{1/3})) traces [De et al., 2017; Fedor Nazarov and Yuval Peres, 2017], several highly efficient algorithms are known [Yuval Peres and Alex Zhai, 2017; Nina Holden et al., 2018] for the average-case version of the problem, in which the source string x is chosen uniformly at random from {0,1}^n. In this paper we consider a generalization of the above-described average-case trace reconstruction problem, which we call average-case population recovery in the presence of insertions and deletions. In this problem, rather than a single unknown source string there is an unknown distribution over s unknown source strings x^1,...,x^s in {0,1}^n, and each sample given to the algorithm is independently generated by drawing some x^i from this distribution and returning an independent trace of x^i. Building on the results of [Yuval Peres and Alex Zhai, 2017] and [Nina Holden et al., 2018], we give an efficient algorithm for the average-case population recovery problem in the presence of insertions and deletions. For any support size 1 <= s <= exp(Theta(n^{1/3})), for a 1-o(1) fraction of all s-element support sets {x^1,...,x^s} subset {0,1}^n, for every distribution D supported on {x^1,...,x^s}, our algorithm can efficiently recover D up to total variation distance at most epsilon with high probability, given access to independent traces of independent draws from D. The running time of our algorithm is poly(n,s,1/epsilon) and its sample complexity is poly (s,1/epsilon,exp(log^{1/3} n)). This polynomial dependence on the support size s is in sharp contrast with the worst-case version of the problem (when x^1,...,x^s may be any strings in {0,1}^n), in which the sample complexity of the most efficient known algorithm [Frank Ban et al., 2019] is doubly exponential in s.

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}ncan be learned under deletion channel noise using 2n(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 ℓ ≤ n1/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].

We present an Õ(n2/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 Ω(n2/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.

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.

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.

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 Õ(k2)/є 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 Ω(2k/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.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f :{0,1} n → {0,1} is a k -junta or ϵ-far from every k -junta must make Ω ˜ ( k 3/2 ) / ϵ) many queries for a wide range of parameters k and ϵ. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω ˜ ( k 3/2 ) / ϵ queries. Combined with the known existence of an adaptive tester which makes O ( k log k + k /ϵ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

In the problem of high-dimensional convexity testing, there is an unknown set S in the n-dimensional Euclidean space which is promised to be either convex or c-far from every convex body with respect to the standard multivariate normal distribution. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set S as possible. In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples (x,S(x)) where each x is independently drawn from the normal distribution. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant c, our results show that the sample complexity of one-sided convexity testing is exponential in n, while for two-sided convexity testing it is exponential in the square root of n.

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f is a k-junta or epsilon-far from every k-junta must make ~Omega(k^{3/2}/ epsilon) many queries for a wide range of parameters k and epsilon. Our result dramatically improves previous lower bounds from [BGSMdW13,STW15], and is essentially optimal given Blais's non-adaptive junta tester from [Blais08], which makes ~O(k^{3/2})/epsilon queries. Combined with the adaptive tester of [Blais09] which makes O(k log k + k / epsilon) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

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 Õ(n3/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.

Let Addk,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,…,2N-1}, and outputs 1 if and only if a(1) + … + a(k) ≥ 2N. Let MAJt,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 x1 + … + xn ≥ t. The function Addk,N may be viewed as a monotone function that performs addition, and MAJt,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.

We prove a lower bound of Ω(n1/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 Ω(n1/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.

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 algebraic complex-valued functions defined on an arbitrary finite domain. 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 and reaches a natural culmination: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function [Dyer and Greenhill 2000; Bulatov and Grohe 2005; Goldberg et al. 2010; Cai et al. 2013]; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not necessarily symmetric binary function [Dyer et al. 2007; Cai and Chen 2010]; (c) the unweighted form of #CSP is when all functions in F take values in {0, 1} [Bulatov 2008; Dyer and Richerby 2013].

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove 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 utility functions, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter ρ is any constant less than − 1.

The recursive teaching dimension (RTD) of a concept class $C \subseteq \{0, 1\}^n$, introduced by Zilles et al. [ZLHZ11], is a complexity parameter measured by the worst-case number of labeled examples needed to learn any target concept of $C$ in the recursive teaching model. In this paper, we study the quantitative relation between RTD and the well-known learning complexity measure VC dimension (VCD), and improve the best known upper and (worst-case) lower bounds on the recursive teaching dimension with respect to the VC dimension. Given a concept class $C \subseteq \{0, 1\}^n$ with $VCD(C) = d$, we first show that $RTD(C)$ is at most $d 2^{d+1}$. This is the first upper bound for $RTD(C)$ that depends only on $VCD(C)$, independent of the size of the concept class $|C|$ and its~domain size $n$. Before our work, the best known upper bound for $RTD(C)$ is $O(d 2^d \log \log |C|)$, obtained by Moran et al. [MSWY15]. We remove the $\log \log |C|$ factor. We also improve the lower bound on the worst-case ratio of $RTD(C)$ to $VCD(C)$. We present a family of classes $\{ C_k \}_{k \ge 1}$ with $VCD(C_k) = 3k$ and $RTD(C_k)=5k$, which implies that the ratio of $RTD(C)$ to $VCD(C)$ in the worst case can be as large as $5/3$. Before our work, the largest ratio known was $3/2$ as obtained by Kuhlmann [Kuh99]. Since then, no finite concept class $C$ has been known to satisfy $RTD(C) > (3/2) VCD(C)$.

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 Õ(n1/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 Õ(n1/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.

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Ω(k1/d/d) when k(n) ≤ n1/5, and nΩ(k1/5d/d) when k(n)≤ n. The previous best circuit size lower bounds were nkexp(−O(d)) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and nΩ((logk)/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 nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1).

We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set $\mathcal{F}$ of constraint functions satisfies this criterion, then the problem #CSP$(\mathcal{F})$ defined by $\mathcal{F}$ is solvable in polynomial time; if $\mathcal{F}$ does not satisfy this criterion, then the problem is #P-hard. Furthermore, we show that the question of whether a given $\mathcal{F}$ satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains.

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.

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.

We prove a lower bound of Ω(n1/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 ~Ω(n1/5) lower bound for the same problem that was obtained in [6], and is very close to the recent upper bound of ~O(n1/2/ε2) by Khot et al. [13].

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 Ω̅(n1/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}nfor all m ≥ 2. Upper bound: We present an O(n5/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(n7/8) poly(1/ε) queries.

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.

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]."

We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.

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.

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{nO(log n)}, improving the previous best bound of smash{exp(~{O}(n1/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.

We describe new ways to simulate two-party communication protocols to get protocols with potentially less 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 $\tilde{O}(\sqrt{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 $\tilde{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 $\sqrt{n}$ times the communication required for computing one copy of the function. For average case complexity, given any distribution $\mu$ on inputs, computing $n$ copies of the function on $n$ inputs sampled independently according to $\mu$ requires $\sqrt{n}$ times the communication for computing one copy. If $\mu$ is a product distribution, computing $n$ copies on $n$ independent inputs sampled according to $\mu$ 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. Our results give the first compression schemes for general randomized protocols and the first direct sum results in the general setting of randomized and distributional communication complexity, without requiring bound on the number of rounds in the protocol or that the distribution of inputs is independent.

Each symmetric matrix $\mathbf{A}$ over $\mathbb{C}$ defines a graph homomorphism function $Z_{\bf A}(\cdot)$ on undirected graphs. The function $Z_{\mathbf{A}} (\cdot)$ is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and $k$-colorings. We study the computational complexity of $Z_{\mathbf{A}} (\cdot)$ for arbitrary symmetric matrices $\mathbf{A}$ with algebraic complex values. Building on work by Dyer and Greenhill [Random Structures and Algorithms, 17 (2000), pp. 260--289], Bulatov and Grohe [Theoretical Computer Science, 348 (2005), pp. 148--186], and especially the recent beautiful work by Goldberg et al. [SIAM J. Comput., 39 (2010), pp. 3336--3402], we prove a complete dichotomy theorem for this problem. We show that $Z_{\mathbf{A}} (\cdot)$ is either computable in polynomial-time or \#P-hard, depending explicitly on the matrix $\mathbf{A}$. We further prove that the tractability criterion on $\mathbf{A}$ is polynomial-time decidable.

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

We prove a complexity dichotomy theorem for all non-negatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems, including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the #CSP problem defined by F is solvable in polynomial time; if it does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous tractability criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra and represents a departure from Universal Algebra, the dominant methodology in recent years.

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 ZA(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.

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.

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.

We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: —Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. —The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are PPAD -hard to compute.

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=(xij) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of xij's, and the equality is in F [X]. Mignon and Ressayre (2004) [11] proved a quadratic lower bound m=Ω(n2) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠2.

We prove a new discrete fixed point theorem for direction-preserving functions defined on integer points, based on a novel characterization of boundary conditions for the existence of fixed points. The theorem allows us to derive an improved algorithm for finding such a fixed point. We also develop a new lower bound proof technique. Together, they allow us to derive an asymptotic matching bound for the problem of finding a fixed point in a hypercube of any constantly bounded finite dimension. Exploring a linkage with the approximation version of the continuous fixed point problem, we obtain asymptotic matching bounds for the complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions. It settles a fifteen-years-old open problem of Hirsch, Papadimitriou, and Vavasis by improving both the upper and lower bounds. Our characterization for the existence of a fixed point is also applicable to functions defined on nonconvex domains, which makes it a potentially useful tool for the design and analysis of algorithms for fixed points in general domains.

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

Even though many people thought the problem of finding Nash equilibria is hard in general, and it has been proven so for games among three or more players recently, it's not clear whether the two-player case can be shown in the same class of PPAD-complete problems. We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete

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.

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.