The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n1+isin for every isin>0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields,...
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity,...
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let Repsiv(f) and Dmuepsiv(f) denote the randomized and mu-distributional communication complexities off, respectively (e a small constant). Yao's well-known minimax principle states that Repsiv(f) = maxmu{Dmuepsiv(f)}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the...
We show that hard sets S for NP must have exponential density, i.e. |S=n| ges 2nepsi for some isin > 0 and infinitely many n, unless coNP sube NP/poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n1-isin queries. In addition we study the instance complexity o/NP- hard problems and show that hard sets also have an exponential amount of instances...
We revisit the computational power of constant width polynomial size planar nondeterministic branching programs. We show that they are capable of computing any function computed by a Pi2 o CC0 o AC0 circuit in polynomial size. In the quasipolynomial size setting we obtain a characterization of ACC0 by constant width planar non-deterministic branching programs.
We show that disjointness requires randomized communication Omega(n1/(k+1)/22k) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (log n/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2nOmega(1) lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial...
We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant mu Gt 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 - (log n)-mu fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm...
We study the complexity of deciding whether a given homogeneous multivariate polynomial has a non- trivial root over a finite field. Given a homogeneous algebraic circuit C that computes an n- variate polynomial p(x) of degree d over a finite field Fq, we wish to determine if there exists a nonzero xisinFqn with C(x)=0. For constant n there are known algorithms for doing this efficiently. However...
We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced...
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can...
In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f(xmacr) = Sigmai=1k hi(xmacr) ldr gi(xmacr), where each hi is a polynomial that depends on...
A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et al. [N. Alon et al., 2003] had conjectured that the presence of a single low weight code in the dual, and "2-transitivity" of the code (i.e., the code is invariant under a 2-transitive...
Using ideas from automata theory we design a new efficient (deterministic) identity test for the noncommutative polynomial identity testing problem (first introduced and studied in [RS05, BW05]). More precisely, given as input a noncommutative circuit C{x1, ldrldrldr , xn} computing a polynomial in F{x1, ldrldrldr , xn} of degree d with at most t monomials, where the variables xi are noncommuting,...
We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the unique games conjecture. Specifically, we show that a predicate P is approximation resistant if there exists a balanced pairwise independent distribution over [q]k whose support is contained in the set of satisfying assignments...
In this paper we study the individual communication complexity of the following problem. Alice receives an input string x and Bob an input string y, and Alice has to output y. For deterministic protocols it has been shown in Buhrman et al. (2004), that C(y) many bits need to be exchanged even if the actual amount of information C(y|x) is much smaller than C(y). It turns out that for randomised protocols...
We give the first exponential separation between quantum and classical multi-party communication complexity in the (non-interactive) one-way and simultaneous message passing settings. For every k, we demonstrate a relational communication problem between k parties that can be solved exactly by a quantum simultaneous message passing protocol of cost O (log n) and requires protocols of cost nc/k2, where...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.