Prange’s information set algorithm is a well-known decoding algorithm for linear codes. It decodes corrupted codewords of most 𝔽₂-linear codes C of message length n up to relative error rate O(log n / n) in poly(n) time. We show that the error rate can be improved to O((log n)² / n), provided: (1) the decoder has access to a polynomial-length advice string that depends on C only, and (2) C is n^{-Ω(1)}-balanced. As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate. Our main technical result is that the Hamming weight of Hw, where the rows of H are a random sample of short dual codewords, measures the proximity of a received word w to the code in the regime of interest. Given such H as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding Hw for an arbitrary polynomial-size advice matrix H.

Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for n > m, a scaled random projection A from ℝn to ℝm is an approximate isometry on any set S of size at most exponential in m. If S is larger, however, its points can contract arbitrarily under A. In particular, the hypergrid ([−B, B] ∩ ℤ)n is expected to contain a point that is contracted by a factor of κstat = Θ(B)−1/α, where α = m/n.

Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions.

While standard evaluation scores for generative models are mostly reference-based, a reference-dependent assessment of generative models could be generally difficult due to the unavailability of applicable reference datasets. Recently, the reference-free entropy scores, VENDI and RKE, have been proposed to evaluate the diversity of generated data. However, estimating these scores from data leads to significant computational costs for large-scale generative models. In this work, we leverage the random Fourier features framework to reduce the metrics' complexity and propose the *Fourier-based Kernel Entropy Approximation (FKEA)* method. We utilize FKEA's approximated eigenspectrum of the kernel matrix to efficiently estimate the mentioned entropy scores. Furthermore, we show the application of FKEA's proxy eigenvectors to reveal the method's identified modes in evaluating the diversity of produced samples. We provide a stochastic implementation of the FKEA assessment algorithm with a complexity $O(n)$ linearly growing with sample size $n$. We extensively evaluate FKEA's numerical performance in application to standard image, text, and video datasets. Our empirical results indicate the method's scalability and interpretability applied to large-scale generative models. The codebase is available at [https://github.com/aziksh-ospanov/FKEA](https://github.com/aziksh-ospanov/FKEA).

We consider the following question of bounded simultaneous messages (BSM) protocols: Can computationally unbounded Alice and Bob evaluate a function f(x,y) of their inputs by sending polynomial-size messages to a computationally bounded Carol? The special case where f is the mod-2 inner-product function and Carol is bounded to AC⁰ has been studied in previous works. The general question can be broadly motivated by applications in which distributed computation is more costly than local computation. In this work, we initiate a more systematic study of the BSM model, with different functions f and computational bounds on Carol. In particular, we give evidence against the existence of BSM protocols with polynomial-size Carol for naturally distributed variants of NP-complete languages.

A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC^0 function distinguish between two such sources when k is big, say k = n^{0.1}? Braverman’s theorem (Commun. ACM 2011) implies a negative answer when X is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general. We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular: - There exist Ω(√n)-indistinguishable X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y that are samplable by degree-d polynomial maps are ε-indistinguishable by OR for all sufficiently large n. Moreover, f(1, ε) = ⌈log(1/ε)⌉ + 1 and f(2, ε) = O(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ circuits. Finally, we motivate the question and our results by presenting applications of positive results to low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.

A function f(x₁, … , x_n) from a product domain 𝒟₁ × ⋯ × 𝒟_n to an abelian group 𝒢 is a direct sum if it is of the form f₁(x₁) + ⋯ + f_n(x_n). We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. This generalizes a result of Dinur and Golubev (RANDOM 2019) which is tailored to the target group 𝒢 = ℤ₂. As a special case, we obtain an optimal affinity test for 𝒢-valued functions on domain {0, 1}ⁿ under product measure. Our analysis relies on the hypercontractivity of the binary erasure channel. We also study the testability of function partitionability over product domains into disjoint components. A 𝒢-valued f(x₁, … , x_n) is k-direct sum partitionable if it can be written as a sum of functions over k nonempty disjoint sets of inputs. A function f(x₁, … , x_n) with unstructured product range ℛ^k is direct product partitionable if its outputs depend on disjoint sets of inputs. We show that direct sum partitionability and direct product partitionability are one-sided error testable with O((n - k)(log n + 1/ε) + 1/ε) adaptive queries and O((n/ε) log²(n/ε)) nonadaptive queries, respectively. Both bounds are tight up to the logarithmic factors for constant ε even with respect to adaptive, two-sided error testers. We also give a non-adaptive one-sided error tester for direct sum partitionability with query complexity O(kn² (log n)² / ε).

$ $Let $F$ be a multivariate function from a product set $Σ^n$ to an Abelian group $G$. A $k$-partition of $F$ with cost $δ$ is a partition of the set of variables $\mathbf{V}$ into $k$ non-empty subsets $(\mathbf{X}_1, \dots, \mathbf{X}_k)$ such that $F(\mathbf{V})$ is $δ$-close to $F_1(\mathbf{X}_1)+\dots+F_k(\mathbf{X}_k)$ for some $F_1, \dots, F_k$ with respect to a given error metric. We study algorithms for agnostically learning $k$ partitions and testing $k$-partitionability over various groups and error metrics given query access to $F$. In particular we show that $1.$ Given a function that has a $k$-partition of cost $δ$, a partition of cost $\mathcal{O}(k n^2)(δ+ ε)$ can be learned in time $\tilde{\mathcal{O}}(n^2 \mathrm{poly} (1/ε))$ for any $ε> 0$. In contrast, for $k = 2$ and $n = 3$ learning a partition of cost $δ+ ε$ is NP-hard. $2.$ When $F$ is real-valued and the error metric is the 2-norm, a 2-partition of cost $\sqrt{δ^2 + ε}$ can be learned in time $\tilde{\mathcal{O}}(n^5/ε^2)$. $3.$ When $F$ is $\mathbb{Z}_q$-valued and the error metric is Hamming weight, $k$-partitionability is testable with one-sided error and $\mathcal{O}(kn^3/ε)$ non-adaptive queries. We also show that even two-sided testers require $Ω(n)$ queries when $k = 2$. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.

The $ε$-approximate degree $deg_ε(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $ε$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly $k$-wise indistinguishable, but are distinguishable by $f$ with advantage $1 - ε$. Our contributions are: We give a simple new construction of a dual polynomial for the AND function, certifying that $deg_ε(f) \geq Ω(\sqrt{n \log 1/ε})$. This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the $1/3$-approximate degree of any read-once DNF is $Ω(\sqrt{n})$. We show that any pair of symmetric distributions on $n$-bit strings that are perfectly $k$-wise indistinguishable are also statistically $K$-wise indistinguishable with error at most $K^{3/2} \cdot \exp(-Ω(k^2/K))$ for all $k < K < n/64$. This implies that any symmetric function $f$ is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-$K$ coalitions with statistical error $K^{3/2} \exp(-Ω(deg_{1/3}(f)^2/K))$ for all values of $K$ up to $n/64$ simultaneously. Previous secret sharing schemes required that $K$ be determined in advance, and only worked for $f=$ AND. Our analyses draw new connections between approximate degree and concentration phenomena. As a corollary, we show that for any $d < n/64$, any degree $d$ polynomial approximating a symmetric function $f$ to error $1/3$ must have $\ell_1$-norm at least $K^{-3/2} \exp({Ω(deg_{1/3}(f)^2/d)})$, which we also show to be tight for any $d > deg_{1/3}(f)$. These upper and lower bounds were also previously only known in the case $f=$ AND.

We study a general Omniscient Arbitrarily Varying Channel (AVC) problem where Alice wishes to communicate a message to receiver Bob by inputting a length-n vector x to a channel. Jammer James observes x, and as a function of x chooses a state sequence s. Bob observes y (such that channel inputs and outputs are related component-wise as yi= w(xi,si) for some deterministic function w(.,.)) from which he must estimate m with no error. Input and state constraints determine feasible inputs x and s for Alice and James respectively. In this work we characterize when a positive communication rate is possible.We first show that the capacity of any such AVC completely depends upon the relationship between a confusability set, and the set of completely-positive-self-couplings (both are convex sets of certain single-letter probability distributions). Our main result provides essentially matching necessary and sufficient conditions for capacity positivity; we show that the zero-error capacity of an AVC is positive if there are completely-positive-self-couplings outside the confusability set of the given AVC; and that the AVC capacity is zero if all completely-positive-self couplings are in the interior of this confusability set. Our achievability uses a novel code construction based on completely-positive-self-couplings called cloud codes which are strict generalizations of all known Gilbert-Varshamov (GV) type codes. Our converse is based upon Ramsey-theoretic ideas, a generalization of the Plotkin bound leveraging a known result on the duality of completely positive matrices and copositive matrices, and a Fourier-analytic proof of the non-existence of certain sequences of random variables.

A k-LIN instance is a system of m equations over n variables of the form si1 + · · · + sik = 0 or 1 modulo 2 (each involving k variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are different. In a noisy planted instance, the right-hand side is obtained by evaluating the system on a random planted solution and adding independent noise with some constant bias to each equation; whereas in a random instance, the right-hand side is uniformly random. Alekhnovich (FOCS 2003) conjectured that the two are hard to distinguish when k = 3 and m = O(n). We give a sample-efficient reduction from solving noisy planted k-LIN instances (a sparse-equation version of the Learning Parity with Noise problem) to distinguishing them from random instances. Suppose that m-equation, n-variable instances of the two types are efficiently distinguishable with advantage ε. Then, we show that O(m · (m/ε)2/k)-equation, n-variable noisy planted k-LIN instances are efficiently solvable with probability exp –Õ((m/ε)6/k). Our solver has worse success probability but better sample complexity than Applebaum's (SICOMP 2013). We extend our techniques to show that this can generalize to (possibly non-linear) k-CSPs. The solver is based on a new approximate local list-decoding algorithm for the k-XOR code at large distances. The k-XOR encoding of a function F: ∑ → {–1, 1} is its k-th tensor power Fk(x1, …, xk) = F(x1) · · · F(xk). Given oracle access to a function G that µ-correlates with Fk, our algorithm, say for constant k, outputs the description of a message that Ω(µ1/k)-correlates with F with probability exp(–Õ(µ−4/k)). Previous decoders, for such k, have a worse dependence on µ (Levin, Combinatorica 1987) or do not apply to subconstant µ1/k. We also prove a new XOR lemma for this parameter regime. The decoder and its analysis rely on a new structure-versus-randomness dichotomy for general Boolean-valued functions over product sets, which may be of independent interest.

Let F be a finite alphabet and D be a finite set of distributions over F. A Generalized Santha-Vazirani (GSV) source of type (F, D), introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence (F_1, ..., F_n) in F^n, where F_i is a sample from some distribution d in D whose choice may depend on F_1, ..., F_{i-1}. We show that all GSV source types (F, D) fall into one of three categories: (1) non-extractable; (2) extractable with error n^{-Theta(1)}; (3) extractable with error 2^{-Omega(n)}. We provide essentially randomness-optimal extraction algorithms for extractable sources. Our algorithm for category (2) sources extracts one bit with error epsilon from n = poly(1/epsilon) samples in time linear in n. Our algorithm for category (3) sources extracts m bits with error epsilon from n = O(m + log 1/epsilon) samples in time min{O(m2^m * n),n^{O(|F|)}}. We also give algorithms for classifying a GSV source type (F, D): Membership in category (1) can be decided in NP, while membership in category (3) is polynomial-time decidable.

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on (1) the size of general Boolean formulas, (2) the size of De Morgan formulas, and (3) correlation against small De Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best-known explicit formula lower bounds in all these models. On the other hand, we give a construction of a small-biased function that is tight with respect to lower bound (1) for the relevant range of parameters. We interpret this construction as a natural-type barrier against substantially stronger lower bounds for general formulas.

Two distributions over n-bit strings are (k,delta)-wise indistinguishable if no statistical test that observes k of the n bits can tell the two distributions apart with advantage better than delta. Motivated by secret sharing and cryptographic leakage resilience, we study the existence of pairs of distributions that are (k, delta)-wise indistinguishable, but can be distinguished by some function f of suitably low complexity. We prove bounds tight up to constants when f is the OR function, and tight up to logarithmic factors when f is a read-once uniform AND \circ OR formula, extending previous works that address the perfect indistinguishability case delta = 0. We also give an elementary proof of the following result in approximation theory: If p is a univariate degree-k polynomial such that |p(x)| <= 1 for all |x| <= 1 and p(1) = 1, then l (p) >= 2^{Omega(p'(1)/k)}, where lˆ (p) is the sum of the absolute values of p’s coefficients. A more general 1 statement was proved by Servedio, Tan, and Thaler (2012) using complex-analytic methods. As a secondary contribution, we derive new threshold weight lower bounds for bounded depth AND-OR formulas.

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class AC0 (MOD2). Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications.

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families. These are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on input X is statistically close to uniform.

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in n inputs and arbitrary gates of fan-in at most d = O(n/ log n), the pseudorandom generator uses (1 - Ω(1))n bits of randomness and produces an output that looks 2-Ω(n)-pseudorandom to all such formulas. Our analysis is based on the following lemma. Let P = Mz+e, where M is the parity-check matrix of a sufficiently good binary error-correcting code of constant rate, z is a random string, e is a small-bias distribution, and all operations are modulo 2. Then for every pair of functions f, g: {0,1}n/2→ {0,1} and every equipartition (I, J) of [n], the distribution P is pseudorandom for the pair (f(x|I), g(x|J)), where x|Iand x|Jdenote the restriction of x to the coordinates in / and J, respectively. More generally, our result applies to read-once branching pro- grams of bounded width with arbitrary ordering of the inputs. We show that such branching programs are more powerful distinguishers than those that read their inputs in sequential order: There exist (explicit) pseudorandom distributions that separate these two types of branching programs.

Suppose Alice and Bob receive strings of unbiased independent but noisy bits from some random source. They wish to use their respective strings to extract a common sequence of random bits with high probability but without communicating. How many such bits can they extract? The trivial strategy of outputting the first$k$bits yields an agreement probability of$(1-\varepsilon)^{k}<2^{-1.44k\varepsilon}$, where$\varepsilon$is the amount of noise. We show that no strategy can achieve agreement probability better than$2^{-k\varepsilon/(1-\varepsilon)}$.

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G:\mathbb{F}^s\to\mathbb{F}^n$ that fool polynomials over a finite field $\mathbb{F}$: We stress that the results in (1) and (2) are unconditional, i.e., do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the componentwise sum of d generators for degree-1 polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i.e., linear) polynomials [J. Naor and M. Naor, SIAM J. Comput., 22 (1993), pp. 838–856]. In fact, over small fields such as $\mathbb{F}_2=\{0,1\}$, our results constitute the first progress on these problems since the long-standing generator by Luby, Veličković, and Wigderson [Deterministic approximate counting of depth-2 circuits, in Proceedings of the 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), 1993, pp. 18–24], whose seed length is much bigger: $s=\exp\left(\Omega\left(\sqrt{\log n}\right)\right)$, even for the case of degree-2 polynomials over $\mathbb{F}_2$.

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol perp, which means "I don't know," A central question in average-case complexity is whether every distributional decision problem in N P has an errorless heuristic scheme: This is an algorithm that, for every delta > 0, runs in time polynomial in the instance size and | / delta and answers perp only on a delta fraction of instances. We study the question from the standpoint of hardness amplification and show that If every problem in (NP,U) has errorless heuristic circuits that output the correct answer on n-2/9+omicron(1)-fraction of inputs, then (NP,U) has non-uniform errorless heuristic schemes. If every problem in (NP,U) has randomized errorless heuristic algorithms that output the correct answer on (log n)-1/10+omicron(1)-fraction of inputs, then (NP.W) has randomized errorless heuristic schemes. In both cases, the low-end amplification is achieved by analyzing a new sensitivity property of monotone boolean Junctions in NP. In the non-uniform setting we use a " holographic Junction" introduced by Benjamini, Schramm, and Wilson (STOC 2005). For the uniform setting we introduce a new Junction that can be viewed as an efficient version of Talagrand's "random DNF".

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators G : FsrarrFnthat fool polynomials over a prime field F: (1) a generator that fools degree-2 (i.e., quadratic) polynomials to within error 1/n, with seed length s = O(log n); (2) a generator that fools degree-3 (i.e., cubic) polynomials to within error epsiv, with seed length s = O(Iog|F|n) + f(epsiv, F) where f depends only on epsiv and F (not on n), (3) assuming the "Gowers inverse conjecture," for every d a generator that fools degree-d polynomials to within error epsiv, with seed length, s = O(dldrIog|F|n) + f(d, epsiv, F) where f depends only on d, epsiv, and F (not on n). We stress that the results in (1) and (2) are unconditional, i.e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the component-wise sum of d generators for degree-l polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i.e., linear) polynomials (Naor and Naor; SIAM J. Comput., 1993). In fact, over small fields such as F2= {0,1}, our results constitute the first progress on these problems since the long-standing generator by Luby, Velickovic and Wigderson (ISTCS1993), whose seed length is much bigger: s = exp (Omega(radiclogn)), even for the case of degree-2 polynomials over F2.

We continue the study of noncommutative polynomial identity testing initiated by Raz and Shpilka and present efficient algorithms for the following problems in the noncommutative model: polynomial identity testing: The algorithm gets as an input an arithmetic circuit with the promise that the polynomial it computes has small degree (for instance, a circuit of logarithmic depth or an arithmetic formula) and determines whether or not the output of the circuit is identically zero (as a formal expression). Unlike the algorithm by Raz and Shpilka, our algorithm is black-box (but randomized with one-sided error) and evaluates the circuit over the ring of matrices. In addition, we present query complexity lower bounds for identity testing and explore the possibility of de-randomizing our algorithm. The analysis of our algorithm uses a noncommutative variant of the Schwartz-Zippel test. Minimizing algebraic branching programs: The algorithm gets as an input an algebraic branching program (ABP) and outputs a smallest equivalent ABP. The algorithm is based on Nisan's characterization of ABP complexity, and uses as a sub-routine an algorithm for computing linear dependencies amongst arithmetic formulas, a problem previously studied by the authors.

We investigate constructions of pseudorandom generators that fool polynomial tests of degree d in m variables over finite fields F. Our main construction gives a generator with seed length O(d 4 log m(1 + log(d/ɛ) / log log m) + log |F|) bits that achieves arbitrarily small bias ɛ and works whenever |F | is at least polynomial in d, log m, and 1/ɛ. We also present an alternate construction that uses a seed that can be described by O(c 2 d 8 m 6/(c−2) log(d/ɛ) + log |F|) bits (more precisely, O(c 2 d 8 m 6/(c−2) ) field elements, each chosen from a set of size poly(cd/ɛ), plus two field elements ranging over all of F), works whenever |F | is at least polynomial in c, d, and 1/ɛ, and has the property that every element of the output is a function of at most c field elements in the input. Both generators are computable by small arithmetic circuits. The main tool used in the construction is a reduction that allows us to transform any “dense ” hitting set generator for polynomials into a pseudorandom generator. 1

We consider the problem of testing bipartiteness in the adjacency matrix model. The best known algorithm, due to Alon and Krivelevich, distinguishes between bipartite graphs and graphs that are /spl epsi/-far from bipartite using 0(1//spl epsi//sup 2/) queries. We show that this is optimal for non-adaptive algorithms, up to polylogarithmic factors. We also show a lower bound of /spl Omega/(1//spl epsi//sup 3/2/) for adaptive algorithms.

We consider the problem of positioning data collecting base stations in a sensor network. We show that in general, the choice of positions has a marked influence on the data rate, or equivalently, the power efficiency, of the network. In our model, which is partly motivated by an experimental environmental monitoring system, the optimum data rate for a fixed layout of base stations can be found by a maximum flow algorithm. Finding the optimum layout of base stations, however, turns out to be an NP-complete problem, even in the special case of homogeneous networks. Our analysis of the optimum layout for the special case of the regular grid shows that all layouts that meet certain constraints are equally good. We also consider two classes of random graphs, chosen to model networks that might be realistically encountered, and empirically evaluate the performance of several base station positioning algorithms on instances of these classes. In comparison to manually choosing positions along the periphery of the network or randomly choosing them within the network, the algorithms tested find positions, which significantly improve the data rate and power efficiency of the network.

We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a distribution that can be sampled then coNP is contained in AM/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow show the same conclusion under the stronger assumption that an NP-complete problem has a non-adaptive random self-reduction. Our result shows it is impossible (using non-adaptive reductions) to base the average-case hardness of a problem in NP or the security of a one-way function on the worst-case complexity of an NP-complete problem (unless the polynomial hierarchy collapses).

We consider the problem of testing 3-colorability in the bounded-degree model. We show that, for small enough /spl epsiv/, every tester for 3-colorability must have query complexity /spl Omega/(n). This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An /spl Omega/(/spl radic/n) lower bound was previously known. For one-sided error testers, we also show an /spl Omega/(n) lower bound for testers that distinguish 3-colorable graphs from graphs that are (1/3 - /spl alpha/)-far from 3-colorable, for arbitrarily small /spl alpha/. In contrast, a polynomial time algorithm by Frieze and Jerrum (1997) distinguishes 3-colorable graphs from graphs that are 1/5-far from 3-colorable. As a by-product of our techniques, we obtain tight unconditional lower bounds on the approximation ratios achievable by sublinear time algorithms for Max E3SAT, Max E3LIN-2 and other problems.