Back to search

Georgia Institute of Technology

Computing with Polynomials over Composites

Abstract

dc:description.abstract

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 lower bounds 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 turns out to be very different from the prime case. Making progress on these problems seems to require a better understanding of polynomials over composites. In this thesis, we address some such "prime vs. composite" problems from algorithms, complexity and combinatorics, and the surprising connections 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 equivalence allows us to use techniques from communication complexity and number theory to prove degree bounds. We use these to give the first tight degree 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.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gopalan, Parikshit
Advisor dc:contributor.advisor
  • Lipton, Richard J.
Committee members dc:contributor.committeemember
  • Randall, Dana
  • Tetali, Prasad
  • Thomas, Robin
  • Basu, Saugata
  • Khot, Subhash

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/11564

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gopalan, Parikshit. Computing with Polynomials over Composites. Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/11564