Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal when the outcome of each comparison is error-free. However, many real-world sorting applications operate in scenarios where the outcome of each comparison can be noisy. In this work, we explore settings where a bounded number of comparisons are potentially corrupted by erroneous agents, resulting in arbitrary, adversarial outcomes. We model the sorting problem as a query-limited tournament graph where edges involving erroneous nodes may yield arbitrary results. Our primary contribution is a randomized algorithm inspired by quick-sort that, in expectation, produces an ordering close to the true total order while only querying Õ(n) edges. We achieve a distance from the target order π within (3 + ε)|B|, where B is the set of erroneous nodes, balancing the competing objectives of minimizing both query complexity and misalignment with π. Our algorithm needs to carefully balance two aspects - identify a pivot that partitions the vertex set evenly and ensure that this partition is "truthful" and yet query as few "triangles" in the graph G as possible. Since the nodes in B can potentially hide in an intricate manner, our algorithm requires several technical steps that ensure that progress is made in each recursive step. Additionally, we demonstrate significant implications for the Ulam-k-Median problem. This is a classical clustering problem where the metric is defined on the set of permutations on a set of d elements. Chakraborty, Das, and Krauthgamer gave a (2-ε) FPT approximation algorithm for this problem, where the running time is super-linear in both n and d. We give the first (2-ε) FPT linear time approximation algorithm for this problem. Our main technical result gives a strengthening of the results in Chakraborty et al. by showing that a good 1-median solution can be obtained from a constant-size random sample of the input. We use our robust sorting framework to find a good solution from such a random sample. We feel that the notion of robust sorting should have applications in several such settings.

$D^2$-sampling is a fundamental component of sampling-based clustering algorithms such as $k$-means++. Given a dataset $V \subset \mathbb{R}^d$ with $N$ points and a center set $C \subset \mathbb{R}^d$, $D^2$-sampling refers to picking a point from $V$ where the sampling probability of a point is proportional to its squared distance from the nearest center in $C$. The popular $k$-means++ algorithm is simply a $k$-round $D^2$-sampling process, which runs in $O(Nkd)$ time and gives $O(\log{k})$-approximation in expectation for the $k$-means problem. In this work, we give a quantum algorithm for (approximate) $D^2$-sampling in the QRAM model that results in a quantum implementation of $k$-means++ with a running time $\tilde{O}(\zeta^2 k^2)$. Here $\zeta$ is the aspect ratio ( i.e., largest to smallest interpoint distance) and $\tilde{O}$ hides polylogarithmic factors in $N, d, k$. It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(\log{k})$ approximation guarantee. Further, we show that our quantum algorithm for $D^2$-sampling can be dequantized using the sample-query access model of Tang (PhD Thesis, Ewin Tang, University of Washington, 2023). This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + \tilde{O}(\zeta^2k^2d)$, where the $O(Nd)$ term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-$k$-means++ on large datasets with bounded aspect ratio. Finally, we use our quantum $D^2$-sampling with the known $ D^2$-sampling-based classical approximation scheme to obtain the first quantum approximation scheme for the $k$-means problem with polylogarithmic running time dependence on $N$.

Coresets for k-means and k-median problems yield a small summary of the data, which preserves the clustering cost with respect to any set of k centers. Recently coresets have also been constructed for constrained k-means and k-median problems. However, the notion of coresets has the drawback that (i) they can only be applied in settings where the input points are allowed to have weights, and (ii) in general metric spaces, the size of the coresets can depend logarithmically on the number of points. The notion of weak coresets, which has less stringent requirements than coresets, has been studied in the context of classical k-means and k-median problems. A weak coreset is a pair (J,S) of subsets of points, where S acts as a summary of the point set and J as a set of potential centers. This pair satisfies the properties that (i) S is a good summary of the data as long as the k centers are chosen from J only, and (ii) there is a good choice of k centers in J with a cost close to the optimal cost. We develop this framework, which we call universal weak coresets, for constrained clustering settings. In conjunction with recent coreset constructions for constrained settings, our designs give greater data compression, are conceptually simpler, and apply to a wide range of constrained k-median and k-means problems.

We consider the capacitated clustering problem in general metric spaces where the goal is to identify $k$ clusters and minimize the sum of the radii of the clusters (we call this the Capacitated-$k$-sumRadii problem). We are interested in fixed-parameter tractable (FPT) approximation algorithms where the running time is of the form $f(k) \cdot \text{poly}(n)$, where $f(k)$ can be an exponential function of $k$ and $n$ is the number of points in the input. In the uniform capacity case, Bandyapadhyay et al. recently gave a $4$-approximation algorithm for this problem. Our first result improves this to an FPT $3$-approximation and extends to a constant factor approximation for any $L_p$ norm of the cluster radii. In the general capacities version, Bandyapadhyay et al. gave an FPT $15$-approximation algorithm. We extend their framework to give an FPT $(4 + \sqrt{13})$-approximation algorithm for this problem. Our framework relies on a novel idea of identifying approximations to optimal clusters by carefully pruning points from an initial candidate set of points. This is in contrast to prior results that rely on guessing suitable points and building balls of appropriate radii around them. On the hardness front, we show that assuming the Exponential Time Hypothesis, there is a constant $c > 1$ such that any $c$-approximation algorithm for the non-uniform capacity version of this problem requires running time $2^{Ω\left(\frac{k}{polylog(k)} \right)}$.

Constrained clustering problems generalize classical clustering formulations, e.g., $k$-median, $k$-means, by imposing additional constraints on the feasibility of clustering. There has been significant recent progress in obtaining approximation algorithms for these problems, both in the metric and the Euclidean settings. However, the outlier version of these problems, where the solution is allowed to leave out $m$ points from the clustering, is not well understood. In this work, we give a general framework for reducing the outlier version of a constrained $k$-median or $k$-means problem to the corresponding outlier-free version with only $(1+\varepsilon)$-loss in the approximation ratio. The reduction is obtained by mapping the original instance of the problem to $f(k,m, \varepsilon)$ instances of the outlier-free version, where $f(k, m, \varepsilon) = \left( \frac{k+m}{\varepsilon}\right)^{O(m)}$. As specific applications, we get the following results: - First FPT (in the parameters $k$ and $m$) $(1+\varepsilon)$-approximation algorithm for the outlier version of capacitated $k$-median and $k$-means in Euclidean spaces with hard capacities. - First FPT (in the parameters $k$ and $m$) $(3+\varepsilon)$ and $(9+\varepsilon)$ approximation algorithms for the outlier version of capacitated $k$-median and $k$-means, respectively, in general metric spaces with hard capacities. - First FPT (in the parameters $k$ and $m$) $(2-δ)$-approximation algorithm for the outlier version of the $k$-median problem under the Ulam metric. Our work generalizes the known results to a larger class of constrained clustering problems. Further, our reduction works for arbitrary metric spaces and so can extend clustering algorithms for outlier-free versions in both Euclidean and arbitrary metric spaces.

The Euclidean $k$-median problem is defined in the following manner: given a set $\mathcal{X}$ of $n$ points in $\mathbb{R}^{d}$, and an integer $k$, find a set $C \subset \mathbb{R}^{d}$ of $k$ points (called centers) such that the cost function $Φ(C,\mathcal{X}) \equiv \sum_{x \in \mathcal{X}} \min_{c \in C} \|x-c\|_{2}$ is minimized. The Euclidean $k$-means problem is defined similarly by replacing the distance with squared distance in the cost function. Various hardness of approximation results are known for the Euclidean $k$-means problem. However, no hardness of approximation results were known for the Euclidean $k$-median problem. In this work, assuming the unique games conjecture (UGC), we provide the first hardness of approximation result for the Euclidean $k$-median problem. Furthermore, we study the hardness of approximation for the Euclidean $k$-means/$k$-median problems in the bi-criteria setting where an algorithm is allowed to choose more than $k$ centers. That is, bi-criteria approximation algorithms are allowed to output $βk$ centers (for constant $β>1$) and the approximation ratio is computed with respect to the optimal $k$-means/$k$-median cost. In this setting, we show the first hardness of approximation result for the Euclidean $k$-median problem for any $β< 1.015$, assuming UGC. We also show a similar bi-criteria hardness of approximation result for the Euclidean $k$-means problem with a stronger bound of $β< 1.28$, again assuming UGC.

We generalise the results of Bhattacharya et al. [Bhattacharya et al., 2018] for the list-k-means problem defined as - for a (unknown) partition X₁, ..., X_k of the dataset X ⊆ ℝ^d, find a list of k-center-sets (each element in the list is a set of k centers) such that at least one of k-center-sets {c₁, ..., c_k} in the list gives an (1+ε)-approximation with respect to the cost function min_{permutation π} [∑_{i = 1}^{k} ∑_{x ∈ X_i} ||x - c_{π(i)}||²]. The list-k-means problem is important for the constrained k-means problem since algorithms for the former can be converted to {PTAS} for various versions of the latter. The algorithm for the list-k-means problem by Bhattacharya et al. is a D²-sampling based algorithm that runs in k iterations. Making use of a constant factor solution for the (classical or unconstrained) k-means problem, we generalise the algorithm of Bhattacharya et al. in two ways - (i) for any fixed set X_{j₁}, ..., X_{j_t} of t ≤ k clusters, the algorithm produces a list of (k/(ε))^{O(t/(ε))} t-center sets such that (w.h.p.) at least one of them is good for X_{j₁}, ..., X_{j_t}, and (ii) the algorithm runs in a single iteration. Following are the consequences of our generalisations: 1) Faster PTAS under stability and a parameterised reduction: Property (i) of our generalisation is useful in scenarios where finding good centers becomes easier once good centers for a few "bad" clusters have been chosen. One such case is clustering under stability of Awasthi et al. [Awasthi et al., 2010] where the number of such bad clusters is a constant. Using property (i), we significantly improve the running time of their algorithm from O(dn³) (k log{n})^{poly(1/(β), 1/(ε))} to O (dn³ (k/(ε)) ^{O(1/βε²)}). Another application is a parameterised reduction from the outlier version of k-means to the classical one where the bad clusters are the outliers. 2) Streaming algorithms: The sampling algorithm running in a single iteration (i.e., property (ii)) allows us to design a constant-pass, logspace streaming algorithm for the list-k-means problem. This can be converted to a constant-pass, logspace streaming PTAS for various constrained versions of the k-means problem. In particular, this gives a 3-pass, polylog-space streaming PTAS for the constrained binary k-means problem which in turn gives a 4-pass, polylog-space streaming PTAS for the generalised binary 𝓁₀-rank-r approximation problem. This is the first constant pass, polylog-space streaming algorithm for either of the two problems. Coreset based techniques, which is another approach for designing streaming algorithms in general, is not known to work for the constrained binary k-means problem to the best of our knowledge.

The Metric $k$-median problem over a metric space $(\mathcal{X}, d)$ is defined as follows: given a set $L \subseteq \mathcal{X}$ of facility locations and a set $C \subseteq \mathcal{X}$ of clients, open a set $F \subseteq L$ of $k$ facilities such that the total service cost, defined as $Φ(F, C) \equiv \sum_{x \in C} \min_{f \in F} d(x, f)$, is minimised. The metric $k$-means problem is defined similarly using squared distances. In many applications there are additional constraints that any solution needs to satisfy. This gives rise to different constrained versions of the problem such as $r$-gather, fault-tolerant, outlier $k$-means/$k$-median problem. Surprisingly, for many of these constrained problems, no constant-approximation algorithm is known. We give FPT algorithms with constant approximation guarantee for a range of constrained $k$-median/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a $(3+\varepsilon)$-approximation and $(9+\varepsilon)$-approximation for the constrained versions of the $k$-median and $k$-means problem respectively in FPT time. In many practical settings of the $k$-median/means problem, one is allowed to open a facility at any client location, i.e., $C \subseteq L$. For this special case, our algorithm gives a $(2+\varepsilon)$-approximation and $(4+\varepsilon)$-approximation for the constrained versions of $k$-median and $k$-means problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constant-pass log-space streaming algorithm.

Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind "do two given points belong to the same optimal cluster?", where the answers to these queries are assumed to be consistent with a unique optimal solution. There are many clustering contexts where such same cluster queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of the k-means clustering problem, with additional margin assumption, can be solved efficiently if one is allowed to make O(k^2 log{k} + k log{n}) same-cluster queries. This is interesting since the k-means problem, even with the margin assumption, is NP-hard. In this paper, we extend the work of Ashtiani et al. to the approximation setting by showing that a few of such same-cluster queries enables one to get a polynomial-time (1+eps)-approximation algorithm for the k-means problem without any margin assumption on the input dataset. Again, this is interesting since the k-means problem is NP-hard to approximate within a factor (1+c) for a fixed constant 0 < c < 1. The number of same-cluster queries used by the algorithm is poly(k/eps) which is independent of the size n of the dataset. Our algorithm is based on the D^2-sampling technique, also known as the k-means++ seeding algorithm. We also give a conditional lower bound on the number of same-cluster queries showing that if the Exponential Time Hypothesis (ETH) holds, then any such efficient query algorithm needs to make Omega (k/poly log k) same-cluster queries. Our algorithm can be extended for the case where the query answers are wrong with some bounded probability. Another result we show for the k-means++ seeding is that a small modification of the k-means++ seeding within the SSAC framework converts it to a constant factor approximation algorithm instead of the well known O(log k)-approximation algorithm.

The classical center based clustering problems such as k-means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. For instance, consider the r -gather clustering problem where there is an additional constraint that each of the clusters should have at least r points or the capacitated clustering problem where there is an upper bound on the cluster sizes. Consider a variant of the k-means problem that may be regarded as a general version of such problems. Here, the optimal clusters O 1, ..., O k are an arbitrary partition of the dataset and the goal is to output k-centers c 1, ..., c k such that the objective function ${\sum }_{i = 1}^{k} {\sum }_{x \in O_{i}} ||x - c_{i}||^{2}$ is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter ε > 0, let ℓ denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1 + ε) approximation w.r.t. the objective function above. In this paper, we show an upper bound on ℓ by giving a randomized algorithm that outputs a list of $2^{\tilde {O}(k/\varepsilon )}$ k-centers. We also give a closely matching lower bound of $2^{\tilde {\Omega }(k/\sqrt {\varepsilon })}$ . Moreover, our algorithm runs in time $O \left (n d \cdot 2^{\tilde {O}(k/\varepsilon )} \right )$ . This is a significant improvement over the previous result of Ding and Xu (2015) who gave an algorithm with running time O(n d ⋅ (log n) k ⋅ 2 p o l y(k/ε)) and output a list of size O((log n) k ⋅ 2 p o l y(k/ε)). Our techniques generalize for the k-median problem and for many other settings where non-Euclidean distance measures are involved.

In-network aggregation is a technique employed in Wireless Sensor Networks (WSNs) to aggregate information flowing from the sensor nodes towards the base station. It helps in reducing the communication overhead on the nodes in the network and thereby increasing the longevity of the network. We study the problem of maintaing integrity of the aggregate value, when the aggregate function is SUM, in the presence of compromised sensor nodes. We focus on one-round, end-to end, secure aggregation protocols and give a strong, formal security defintion. We show that a worst-case lower bound of Ω(n) applies on the congestion (maximum size of message between any two nodes) in such protocols, where n is the number of nodes in the network. This is the first such result showing that the most basic protocols are the best one-round in-network aggregation protocols with respect to congestion. We also show that against a weaker adversary (which does not compromise nodes), we can achieve secure in-network aggregation protocols with a congestion of O(log2n).

We show that any distribution on $\{-1,+1\}^n$ that is k-wise independent fools any halfspace (or linear threshold function) $h:\{-1,+1\}^n\to\{-1,+1\}$, i.e., any function of the form $h(x)=\operatorname{sign}(\sum_{i=1}^{n}w_{i}x_{i}-\theta)$, where the $w_1,\dots,w_n$ and $\theta$ are arbitrary real numbers, with error $\epsilon$ for $k=O(\epsilon^{-2}\log^2(1/\epsilon))$. Our result is tight up to $\log(1/\epsilon)$ factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators $G:\{-1,+1\}^s\to\{-1,+1\}^n$ that fool halfspaces. Specifically, we fool halfspaces with error $\epsilon$ and seed length $s=k\cdot\log n=O(\log n\cdot\epsilon^{-2}\log^2(1/\epsilon))$. Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180–209].

The classical direct product theorem for circuits says that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each $x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the direct product theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and $\epsilon$, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes $f^k$ on at least $\epsilon$ fraction of inputs, the algorithm A outputs with probability at least $3/4$ a list of $O(1/\epsilon)$ circuits such that at least one of the circuits on the list computes f on more than $1-\delta$ fraction of inputs, for $\delta=O((\log1/\epsilon)/k)$; moreover, each output circuit is an $\mathsf{AC}^0$ circuit (of size $\mathrm{poly}(n,k,\log1/\delta,1/\epsilon)$), with oracle access to the circuit C. Using the Goldreich–Levin decoding algorithm [O. Goldreich and L. A. Levin, A hard-core predicate for all one-way functions, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, 1989, pp. 25–32], we also get a fully uniform version of Yao's XOR lemma [A. C. Yao, Theory and applications of trapdoor functions, in Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, Chicago, 1982, pp. 80–91] with optimal parameters, up to constant factors. Our results simplify and improve those in [R. Impagliazzo, R. Jaiswal, and V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 2006, pp. 187–196]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of “derandomized” direct product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

We show that any distribution on {-1,+1}nthat is k-wise independent fools any halfspace (a.k.a. threshold) h : {-1,+1}n¿ {-1,+1}, i.e., any function of the form h(x) = sign(¿i=1nwiXi- ¿) where the w1,..., wn, ¿ are arbitrary real numbers, with error ¿ for k = O(¿-2log2(1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G : {-1,+1}s¿ {-1,+1}nthat fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿-2log2(1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are: a derivation of an extremely simple pseudo-approximation batch algorithm for k-means, in which the algorithm is allowed to output more than k centers (based on the recent k-means++"), and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (fitting in memory) and combined in a hierarchical manner. Empirical evaluations on real and simulated data reveal the practical utility of our method."

Given a message $msg\in\{0,1\}^N$, its k-wise direct product encoding is the sequence of k-tuples $(msg(i_1),\dots,msg(i_k))$ over all possible k-tuples of indices $(i_1,\dots,i_k)\in\{1,\dots,N\}^k$. We give an efficient randomized algorithm for approximate local list-decoding of direct product codes. That is, given oracle access to a word which agrees with a k-wise direct product encoding of some message $msg\in\{0,1\}^N$ in at least $\epsilon\geqslant{poly}(1/k)$ fraction of positions, our algorithm outputs a list of ${poly}(1/\epsilon)$ strings that contains at least one string $msg'$ which is equal to $msg$ in all but at most $k^{-\Omega(1)}$ fraction of positions. The decoding is local in that our algorithm outputs a list of Boolean circuits so that the jth bit of the ith output string can be computed by running the ith circuit on input j. The running time of the algorithm is polynomial in $\log N$ and $1/\epsilon$. In general, when $\epsilon>e^{-k^{\alpha}}$ for a sufficiently small constant $\alpha>0$, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in $1/\epsilon$, i.e., $(1/\epsilon)^{{poly}\log1/\epsilon}$. As an application of our decoding algorithm, we get uniform hardness amplification for ${P}^{{NP}_{\parallel}}$, the class of languages reducible to ${NP}$ through one round of parallel oracle queries: If there is a language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1-1/n^{\Omega(1)}$ fraction of inputs, then there is another language in ${P}^{{NP}_{\parallel}}$ that cannot be decided by any ${BPP}$ algorithm on more than $1/2+1/n^{\omega(1)}$ fraction of inputs.

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1}n -> {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function fk(x1,...,xk)=(f(x1),...,f(xk)) (where each xi -> {0,1}n) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the Direct-Product Theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and ε, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes fk on at least ε fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1-δ fraction of inputs, for δ = O((log 1/ε)/k). Moreover, each output circuit is an AC0 circuit (of size poly(n,k,log 1/δ,1/ε)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [5], we also get a fully uniform version of Yao's XOR Lemma [18] with optimal parameters, up to constant factors. Our results simplify and improve those in [10]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.

We consider the problem of approximately locally list-decoding direct product codes. For a parameter k, the k-wise direct product encoding of an N-bit message msg is an Nk-length string over the alphabet {0, l}kindexed by k-tuples (i1, .. ., ik) isin {1,..., N}kso that the symbol at position (i1, .. ., ik) of the codeword is msg(i1)...msg(ik). Such codes arise naturally in the context of hardness amplification of Boolean functions via the direct product lemma (and the closely related Yao 's XOR Lemma), where typically k Lt N (e.g., k = poly log N). We describe an efficient randomized algorithm for approximate local list-decoding of direct product codes. Given access to a word which agrees with the k-wise direct product encoding of some message msg in at least an epsiv fraction of positions, our algorithm outputs a list of poly(l/epsiv) Boolean circuits computing N-bit strings (viewed as truth tables of log N-variable Boolean functions) such that at least one of them agrees with msg in at least 1 - delta fraction of positions, for delta = O(k-0.1), provided that epsiv = Omega(poly(l/k); the running time of the algorithm is polynomial in log N and 1/epsiv. When epsiv > epsivkalphafor a certain constant alpha > 0, we get a randomized approximate list-decoding algorithm that runs in time quasi-polynomial in 1/epsiv (i.e., (1/epsiv)poly log 1epsiv/)By concatenating the k-wise direct product codes with Hadamard codes, we obtain locally list-decodable codes over the binary alphabet, which can be efficiently approximately list-decoded from fewer than frac12 - epsiv fraction of corruptions as long as epsiv = Omega(poly(l/k)). As an immediate application, we get uniform hardness amplification for PNPpar, the class of languages reducible to NP through one round of parallel oracle queries: If there is a language in PNPparthat cannot be decided by any BPP algorithm on more that 1 $1/nOmega(1)fraction of inputs, then there is another language in PNPparthat cannot be decided by any BPP algorithm on more than frac12 + 1/nomega(1)fraction of inputs