In the last twenty years, algebraic techniques have been applied with great success to several areas in theoretical computer science. However, for many problems involving modular counting, there is a huge gap in our understanding depending on whether the modulus is prime or composite.A prime example is the problem of showing lowerbounds for circuits with Mod gates in circuit complexity. Proof techniques that work well for primes break down over composites. Moreover, in some cases, the problem for composites turnsout to be very different from the prime case. Making progress on these problems seems to require a better understanding of polynomials overcomposites. In this thesis, we address some such "prime vs. composite" problems from algorithms, complexity and combinatorics, and the surprisingconnections between them. We consider the complexity-theoretic problem of computing Boolean functions using polynomials modulo composites. We show that symmetric polynomials can viewed as simultaneous communication protocols. This equivalenceallows us to use techniques from communication complexity and number theory to prove degree bounds. We use these to give the first tightdegree bounds for a number of Boolean functions.We consider the combinatorial problem of explicit construction of Ramsey graphs. We present a simple construction of such graphs using polynomials modulo composites. This approach gives a unifying view of many known constructions,and explains why they all achieve the same bound.We show that certain approaches to this problem cannot give better bounds.Finally, we consider the algorithmic problem of interpolation for polynomials modulo composites. We present the first query-efficient algorithms for interpolation and learning under a distribution. These results rely on some new structural results about such polynomials.
PDF
download
878987797
028-85220240
