Show simple item record

dc.contributor.authorGopalan, Parikshiten_US
dc.date.accessioned2006-09-01T19:34:12Z
dc.date.available2006-09-01T19:34:12Z
dc.date.issued2006-07-07en_US
dc.identifier.urihttp://hdl.handle.net/1853/11564
dc.description.abstractIn 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.en_US
dc.format.extent1288569 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectPolynomialsen_US
dc.subjectNumber theory
dc.subjectComposites
dc.subjectPrimes
dc.subjectAlgebra
dc.subjectComputational complexity
dc.subjectComputer science
dc.titleComputing with Polynomials over Compositesen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentComputingen_US
dc.description.advisorCommittee Chair: Richard J. Lipton; Committee Member: Dana Randall; Committee Member: Prasad Tetali; Committee Member: Robin Thomas; Committee Member: Saugata Basu; Committee Member: Subhash Khoten_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record