14452021
On Data Structures and Asymmetric Communication Complexity
In this paper we consider two-party communication complexity, the “asymmetric case”, when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our “round elimination” lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the “round reduction” techniques used in many previous lower bound proofs.
5341041
Lower bounds on arithmetic circuits via partial derivatives
In this paper we describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials (that hold over fields of characteristic zero) and iterated matrix products (that hold for all fields).
17896683
On the second eigenvalue of hypergraphs
where n = |V |. Let G = (V,E) be a 3-uniform hypergraph; i.e. E is a subset of subsets of V of size 3. We consider the space, L(V ), of real valued functions on V with the usual inner product; let e1, . . . , en be the standard basis for L(V ), where ei takes the value 1 on the i-th vertex of V and 0 elsewhere. It is natural to construct from G a trilinear form, that is a map from τ , mapping triples of vectors in L(V ) to R, namely τ  n ∑
10033815
Expanders In Group Algebras
Let G be a finite group and let p be a prime such that (p, |G|) = 1. We study conditions under which the Abelian group $$\Bbb F$$p[G] has a few G-orbits whose union generate it as an expander (equivalently, all the discrete Fourier coefficients (in absolute value) of this generating set are bounded away uniformly from one).We prove a (nearly sharp) bound on the distribution of dimensions of irreducible representations of G which implies the existence of such expanding orbits. We further show a class of groups for which such a bound follows from the expansion properties of G. Together, these lead to a new iterative construction of expanding Cayley graphs of nearly constant degree.
7565108
Space complexity in propositional calculus
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to space bounded Turing machines with a read-only input tape, and such popular propositional proof systems as Resolution, Polynomial Calculus and Frege systems. We study two different space measures. The first, introduced by [5] for Resolution and extended here to other systems, is the structured measure which counts the number of clauses/monomials kept is memory simultaneously. The other is an unstructured °measure related to the number of b i t s describing the memory content. We develop lower bound techniques that enable proving tight linear lower bounds for the first measure, and tight quadratic lower bounds for the second, for large classes of tautologies (including familiar ones like the pigeonhole principle), in both Resolution and (extensions of) Polynomial Calculus. We also prove some structural results concerning the clause space for Resolution and Frege Systems.
45550157
Space Complexity in Propositional Calculus
We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape and such popular propositional proof systems as resolution, polynomial calculus, and Frege systems. We propose two different space measures, corresponding to the maximal number of bits, and clauses/monomials that need to be kept in the memory simultaneously. We prove a number of lower and upper bounds in these models, as well as some structural results concerning the clause space for resolution and Frege systems.
126394795
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
n and 0 < δ < 1, we construct graphs on n nodes such that every two sets of size share an edge, having essentially optimal maximum degree . Using known and new reductions from these graphs, we derive new explicit constructions of:
1.  A k round sorting algorithm using comparisons.
2.  A k round selection algorithm using comparisons.
3.  A depth 2 superconcentrator of size .
4.  A depth k wide-sense nonblocking generalized connector of size .All of these results improve on previous constructions by factors of , and are optimal to within factors of . These results are based on an improvement to the extractor construction of Nisan & Zuckerman: our algorithm extracts an asymptotically optimal number of random bits from a defective random source using a small additional number of truly random bits.