The mean of a random variable can be understood as a *linear* functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating *non-linear* functionals of probability distributions. We propose a \textit{quantum-inside-quantum} algorithm that achieves this speedup for the broad class of nonlinear estimation problems known as nested expectations. Our algorithm improves upon the direct application of the quantum-accelerated multilevel Monte Carlo algorithm introduced by An et. al.. The existing lower bound indicates that our algorithm is optimal up to polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.

We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.

The celebrated Lovász Local Lemma (LLL) guarantees that locally sparse systems always have solutions. The Moser-Tardos Resample algorithm does not only find such a solution in linear time, but its beautiful analysis has greatly enhanced LLL related research [9, 10]. Nevertheless two major questions remain open. How far beyond Lovász's condition can we expect that Resample still performs in polynomial (linear) expected running time? In Resample we have a choice between different constraint-selection strategies. How much does this choice matter? To state the first question correctly is a challenge already. For a solvable fixed instance Resample always comes up with a solution, but the catch is that the number of steps may be very large. We have therefore looked at parameterized instance families and tried to identify phase transitions in terms of these parameters. Perhaps the biggest lesson we have learned is that if we want to see phase transition thresholds, i.e. identify parameter values where Resample “stops working,” we need to understand what happens when Resample does not work. We have noticed that in this case the algorithm settles at a metastable equilibrium (at least for the homogenous instances we have considered), a phenomenon mostly studied for physical systems. Concerning the policies for picking the violated constraints (such as first violated, random violated, recursive fix, etc.), in the context of the grid-coloring problem the methods worked exactly for the same parameter range the number of resample steps differed by no more than 20 percent. All results are experimental, although we discuss a possible reason behind some phenomena.

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

It is a long-standing problem to lower bound the performance of randomized greedy algorithms for maximum matching. Aronson, Dyer, Frieze and Suen [1]studied the modified randomized greedy (MRG) algorithm and proved that it approximates the maximum matching within a factor of at least 1/2 + 1/400,000. They use heavy combinatorial methods in their analysis. We introduce a new technique we call Contrast Analysis, and show a 1/2 + 1/256 performance lower bound for the MRG algorithm. The technique seems to be useful not only for the MRG, but also for other related algorithms.

Algorithmic mechanism design is concerned with designing algorithms for settings where inputs are controlled by selfish agents, and the center needs to motivate the agents to report their true values. In this paper, we study scenarios where the center may be able to verify whether the agents report their preferences (types) truthfully. We first consider the standard model of mechanism design with partial verification, where the set of types that an agent can report is a function of his true type. We explore inherent limitations of this model; in particular, we show that the famous Gibbard--Satterthwaite impossibility result holds even if a manipulator can only lie by swapping two adjacent alternatives in his vote. Motivated by these negative results, we then introduce a richer model of verification, which we term mechanism design with probabilistic verification. In our model, an agent may report any type, but will be caught with some probability that may depend on his true type, the reported type, or both; if an agent is caught lying, he will not get his payment and may be fined. We characterize the class of social choice functions that can be truthfully implemented in this model. We then proceed to study the complexity of finding an optimal individually rational implementation, i.e., one that minimizes the center's expected payment while guaranteeing non-negative utility to the agent, both for truthful and for non-truthful implementation. Our hardness result for non-truthful implementation answers an open question recently posed by Auletta et al. [2011].

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.

Beck's early work [3] gave an efficient version of the Lovász Local Lemma(LLL) with significant compromise in the parameters. Following several improvements [1,7,4,13], Moser [8], and Moser and Tardos [9] obtained asymptotically optimal results in terms of the maximal degree.

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(Γ), where the latter is the collection of those n-ary operations (n= 1,2,...) that keep all constraints in Γ invariant. We show that the algebraic condition boils down to whether there are arbitrarily resilient functions in Pol(Γ). Using this characterization and a result of Dinur, Friedgut and Regev, we give an entirely new and transparent proof to the Hell-Nesetril theorem, which states that for a simple, connected and undirected graph H, the problem CSP(H) is NP-hard if and only if H is non-bipartite. We also introduce another notion of resilience (we call it strong resilience), and we use it to characterize CSP problems that 'do not have the ability to count.' Very recently this class has been shown to be equivalent with the the class of bounded width problems, i.e. the class of CSPs that be described by existential k-pebble games. What emerges from our research, is that certain important algebraic conditions that are usually expressed via identities have equivalent definitions that rely on asymptotic properties of term operations. Our new notions have a potential to show hardness of CSPs (as demonstrated on the Hell-Nesetril theorem), or to prove their tractability.

We present two new quantum algorithms that either find a triangle (a copy of $K_{3}$) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes $\tilde{O}(n^{10/7})$ queries. The second algorithm uses $\tilde{O}(n^{13/10})$ queries and is based on a design concept of Ambainis [in Proceedings of the $45$th IEEE Symposium on Foundations of Computer Science, 2004, pp. 22–31] that incorporates the benefits of quantum walks into Grover Search [L. Grover, in Proceedings of the Twenty‐Eighth ACM Symposium on Theory of Computing, 1996, pp. 212–219]. The first algorithm uses only $O(\log n)$ qubits in its quantum subroutines, whereas the second one uses $O(n)$ qubits. The Triangle Problem was first treated in [H. Buhrman et al., SIAM J. Comput., 34 (2005), pp. 1324–1330], where an algorithm with $O(n+\sqrt{nm})$ query complexity was presented, where m is the number of edges of G.

The priority sampling procedure of N. Duffield, C. Lund and M. Thorup is not only an exciting new approach to sampling weighted data streams, but it has also proven to be highly successful in a variety of practical applications. We resolve the two major issues related to its performance. First we solve the main conjecture of N. Alon, N. Duffield, C. Lund and M. Thorup in [1], which states that the standard deviation for the subset sum estimator obtained from k priority samples is upper bounded by W/√k-1, where W denotes the actual subset sum that the estimator estimates. Although Alon et al. give an O(W/√k-1) upper bound on the standard deviation of the estimator, their formula cannot be used as a performance guarantee in an applied setting, because the constants coming up in their proof are very large. Our constant cannot be improved. We also resolve the conjecture of Duffield, C. Lund and M. Thorup which states that the variance of the priority sampling procedure is not larger than the variance of the threshold sampling procedure with sample size only one smaller. This is the main conjecture in [7]. The conjecture's significance is that the latter procedure is provably optimal within a very general class of sampling algorithms, but unlike priority sampling, it is not practical. Our result therefore certifies that priority sampling offers the unlikely feat of uniting mathematical elegance, (essential) optimality and applicability. Our proof is based on a new integral formula and on very finely tuned telescopic sums.

We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in Špalek & Szegedy (2005) with the realization that these many different formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the formula size, and even, up to a constant multiplicative factor, the probabilistic formula size of f. We show that several formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Håstad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary, culminating with the realization that these many different formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to classical complexity theory. As a surprising application we show that sumPI/sup 2/(f) is a lower bound on the formula size, and even, up to a constant multiplicative factor, the probabilistic formula size of f. We show that several formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khrapchenko, 1971, Koutsoupias, 1993], including a key lemma of [Hastad, 1998], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI/sup 2/(f) remains a lower bound on formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma gives that our methods can also be used to lower bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis [2003], and the collision problem.

We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted.

Let f be an integer valued function on a finite set V. We call an undirected graph G(V,E)a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) find a vertex x ∈ V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form what is the value of f on x? We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous[4] Ald and Aaronson [1] Aar and solves the main open problem in Aar.

We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.

We show how to construct an arrangement of n lines having a monotone path of length O(n2-(d/vlog n)), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language $L\in \{0,1\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\in L$ and rejects it with high probability if w has to be modified in at least $\epsilon n$ positions to create a word in L. The algorithm queries $\tilde{O}(1/\epsilon)$ bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in $1/\epsilon$. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of $\epsilon$. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Query optimizers rely on fast, high-quality estimates of result sizes in order to select between various join plans.Selfjoin sizes of relations provide bounds on the join size of any pairs of such relations.It also indicates the degree of skew in the data, and has been advocated for several estimation procedures.Exact computation of the self-join size requires storage proportional to, the number of distinct attribute values, which may be prohibitively large.In this paper, we study algorithms for tracking (approximate) self-join sizes in limited storage in the presence of insertions and deletions to the relations.Such algorithms detect changes in the degree of skew without an expensive recomputation from the base data.We show that an algorithm based on a tug-ofwar approach provides a more accurate estimation than one based on a sample-and-count approach which is in turn more accurate than a sampling-only approach.Next, we study algorithms for tracking (approximate) join sizes in limited storage; the goal is to maintain a small signature of each relation such that join sizes can be accurately estimated between any pairs of relations.We show that taking random samples for join signatures can lead to inaccurate estimation unless the sample size is quite large; moreover, by a lower bound we show, no other signature scheme can significantly improve upon sampling without further assumptions.These negative results are shown to hold even in the presence of sanity bounds.On the other hand, we present a join signature scheme based on tug-ofwar signatures that probvides guarantees on join size estimation as a function of t:he self-join sizes of the joining relations; this scheme can significantly improve upon the sampling scheme.

We say that a subset T of Z/sup 2/, the two dimensional infinite grid, tiles Z/sup 2/ if we can cover Z/sup 2/ with non-overlapping translates of T. No algorithm is known to decide whether a finite T/spl sube/Z/sup 2/ tiles Z/sup 2/. Here we present two algorithms, one for the case when |T| is prime, and another for the case when |T|=4. Both algorithms generalize to the case, where we replace Z/sup 2/ with all arbitrary finitely generated Abelian group. As a by-product of our results we partially settle the Periodic Tiling Conjecture raised by J. Lagarias and Y. Wang (1997), and we also get the following generalization of a theorem of L.Redei (1965): Let G be a (finite or infinite) Abelian group G with a generator set T of prime cardinality such, that 0/spl isin/T, and there is a set T'/spl sube/G with the property that for every g/spl isin/G there are unique t/spl isin/T, t'/spl isin/T' such that g=t+t'. Then T' can be replaced with a subgroup of G, that also has the above property.

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof” with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length). As a consequence, we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP = P. The class MAX SNP was defined by Papadimitriou and Yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige et al. [1996] and Arora and Safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an N -vertex graph to within a factor of N ε is NP-hard.

The frequency moments of a sequence containing m i elements of type i, for 1 i n, are the numbers Fk = P n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers Fk , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0

) Ilan Newman and Mario Szegedy y Abstract We study 1-round two parties communication complexity games, where private random bits are used. We observe that the existence of good protocols for such games is related to a notion of approximating the matrix that represents the function by a certain low rank matrix. This gives rise to a new notion of rank, analogous of positive rank for 1-round communication complexity. We prove that the identity matrix is non approximable by low rank matrices in this sense. As a corollary we prove that any randomized protocol for the equality function requires \\Omega\\Gamma p n) complexity in the 1-round, private bits model, answering an open question raised by Yao [8]. A corollary is an answer to the following graph theoretic question: Assume a graph on n vertices has a set of N = N (n) cliques and so that for each two different cliques of this set, the number of edges between them is at most 0.1 of the product of their sizes. How large can N be ? ...

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.

A thrackte is a graph that can be drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs.About thirty years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices.We show that a thrackle has at most twice as many edges as vert ices.Some related problems and generalizations are also considered.

We show that any graph of n vertices that can be drawn in the plane with no k+1 pairwise crossing edges has at most cknlog2k−2n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdős, Kupitz, Perles, and others. We also construct two point sets {p1,…,pn}, {q1,…,qn} in the plane such that any piecewise linear one-to-one mapping f:R2→R2 with f(pi)=qi (1≤i≤n) is composed of at least Ω(n2) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.

The /spl theta/ number of Lovasz and the /spl theta//sub 1/2/ of Schrijver, McEliece, Rodemich and Rumsey are convex (semidefinite) programming upper bounds on /spl alpha/(G), the size of a maximal independent set of G. It is known that /spl alpha/(G)/spl les//spl theta//sub 1/2/(G)/spl les//spl theta/(G)/spl les//spl chi/~(G), where /spl chi/~(G) is the clique cover number of G. The above inequalities suggest that perhaps /spl theta//sub 1/2/(G) approximates /spl alpha/(G) from above, and /spl theta/(G) approximates /spl chi/~(G) from below for every graph G. Can this approximation be to within a factor of at most n/sup 1-/spl epsiv// for some fixed /spl epsiv/>0? We show, that the following three conjectures are equivalent: 1. /spl exist//spl epsiv/>0 : /spl theta/(G) approximates /spl alpha/(G) for every G within a factor of n/sup n-/spl epsiv// 2. /spl exist//spl epsiv/>0 : /spl theta/(G) approximates /spl chi/~(G) for every G within a factor of n/sup n-/spl epsiv// 3. /spl exist//spl epsiv/>0 : /spl theta//sub 1/2/(G) approximates /spl alpha/(G) for every G within a factor of n/sup n-/spl epsiv// It is not impossible that /spl theta//sub 1/2/ approximates /spl chi/~(G), but the latter conjecture looks strictly stronger than 1-3. We give however a simple combinatorial reformulation of this one (we cannot find such for 1-3). We rule out some likely candidates for counterexamples to 1-3 by showing that /spl theta/(G) approximates /spl alpha/(G) and /spl chi/~(G) for those graphs G that come from the Hamming scheme.>

An algorithm for vertex-coloring graphs is said to be on-line if each vertex is irrevocably assigned a color before later vertices are considered. We show that for every such algorithm there exists a log n-colorable graph for which the algorithm uses at least 2n/log n colors. This also holds for randomized algorithms, to within a constant factor, against an oblivious adversary. We then show that various means of relaxing the constraints of the on-line model do not reduce these lower bounds. The features include presenting the input in blocks of up to log2 n vertices, recoloring any fraction of the vertices, presorting vertices by degree, and disclosing the adversary's previous coloring.

We study the problem of locality based graph coloring.This problem is motivated by the problem of assigning time slots for broadcast in mobile packet radio networks.This problem has also been studied in the context of distributed and parallel graph coloring [4, 6, 9, 8].In this problem, one has to design a coloring algorithm that assigns a color to a vertex based on the label of the vertex and the labels on its neighbors.Linial proved an upper bound of O(A2 log n) and a lower bound of fl(log log n) on the number of colors needed to locally color an n-vertex graph with maximum vertex degree A [9, 8].His main motivation was that repeated application of local coloring gives a fast algorithm for distributed coloring.He proved that one could get a A2 coloring in O(log* n) steps this way.In this paper we improve upon the bounds for the problem of local coloring.Using a new characterization in terms of a family of set systems we design a randomized algorithm for the problem and prove an upper bound of O(A.2A log log n).An important question left open in Linial's paper was the case of large A. The best lower bound was A + 1. Linial observed that a result of Erdos, Frankl and Furedi implied that his method cannot be applied to reduce the number of colors to below (A~2).We obtain lower bounds that match the upper bounds within a factor that is poly-logarithmic in terms of these bounds.Of particular interest we have very precise bounds for the case when A > 2+.These bounds are useful to obtain a heuristic estimate on the *Researchsupported in part by Ketan Mulmuley's Packard Fellowship.

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP.>

Every boolean function may be represented as a real polynomial. In this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function.

We prove that polynomial time bounded RAMs with the instruction set [shift, +, X, boolean ] accept exactly the languages in PSPACE. This generalizes previous results: [5] showed the same for the instruction set that does not include multiplication, [5] and [7] proved the weaker theorems, that RAMs (and even PRAMs) with this instruction set could be simulated in EXPTAPE. The PRAM result is a simple corollary to our theorems. We also introduce other powerful string-manipulating instructions for RAMs, show a nontrivial simulation of Turing machines by these RAMs, and show that in a sense such simulations are optimal.

The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P.>

. Motivated by Manuel Blum's concept of instance checking, we consider new, very fast and generic mechanisms of checking computations. Our results exploit recent advances in interactive proof protocols [LFKN92], [Sha92], and especially the MIP = NEXP protocol from [BFL91]. We show that every nondeterministic computational task S(x; y), defined as a polynomial time relation between the instance x, representing the input and output combined, and the witness y can be modified to a task S 0 such that: (i) the same instances remain accepted; (ii) each instance/witness pair becomes checkable in polylogarithmic Monte Carlo time; and (iii) a witness satisfying S 0 can be computed in polynomial time from a witness satisfying S. Here the instance and the description of S have to be provided in error-correcting code (since the checker will not notice slight changes). A modification of the MIP proof was required to achieve polynomial time in (iii); the earlier technique yields N O(log log N)...

Article Free Access Share on Functions with bounded symmetric communication complexity and circuits with mod m gates Author: M. Szegedy The Hebrew University, Jerusalem 91904, Israel, Computer Science Department of The University of Chicago The Hebrew University, Jerusalem 91904, Israel, Computer Science Department of The University of ChicagoSearch about this author Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990Pages 278–286https://doi.org/10.1145/100216.100252Published:01 April 1990Publication History 4citation243DownloadsMetricsTotal Citations4Total Downloads243Last 12 Months12Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let ƒ(x1, ···· xk) be a Boolean function that k parties wish to collaboratively evaluate. The i'th party knows each input argument except xi; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board.

We examine a powerful model of parallel computation: polynomial size threshold circuits of bounded depth (the gates compute threshold functions with polynomial weights). Lower bounds are given to separate polynomial size threshold circuits of depth 2 from polynomial size threshold circuits of depth 3, and from probabilistic polynomial size threshold circuits of depth 2. We also consider circuits of unreliable threshold gates, circuits of imprecise threshold gates and threshold quantifiers.