Course Information

CS 760: Topics in Computational Complexity.

The course is aimed at a studying one or more of the following topics in Computational Complexity in detail, with the precise content varying across renderings.
● Boolean and Algebraic circuit complexity lower bounds
● Hardness vs randomness tradeoffs in the Boolean and Algebraic computation
● Computing GCD of Polynomials, Polynomial factorization, Elimination theory, Solving system of Polynomial Equations
● Theory of Error Correcting codes
● Locally decodable/correctable codes and applications
● Lower bounds in communication complexity and connections to Boolean circuit complexity
● PCP theorem and applications to hardness of approximation

More details about content and references can be found on the course webpage.

Depending upon the content, some of the following references might be relevant.
● Boolean Function Complexity by S. Jukna, Springer, 2012
● Algebraic Complexity Theory by P. Burgisser, M. Clausen and M.A. Shokrollahi, Springer, 1997
● Ideals, variety and algorithms by D.A. Cox, J. Little and D. O’Shea, Springer, 2015
● Essential Coding Theory by V. Guruswami, A. Rudra and M. Sudan. ebook: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
● Communication Complexity by A. Rao and A. Yehudayoff, ebbok: https://homes.cs.washington.edu/~anuprao/pubs/book.pdf
● Introduction to Property Testing by O. Goldreich, Cambridge University Press, 2017
● Computational Complexity: A modern approach by S. Arora and B. Barak, Cambridge University Press 2009
● Algebra and Computation, Notes for a course by R. Saptharishi at TIFR Bombay, https://www.tcs.tifr.res.in/~ramprasad/courses/2017-algComp/
Home Page


Desired background - CS 207, CS 213, CS 218, CS721
Other Details

Duration : Full Semester Total Credit : 0
Type : Theory
Autumn Semester 2019-20

Status : Not Offered Instructor : ---
Spring Semester 2019-20

Status : Offered Instructor : Prof. Mrinal Kumar, Prof. Sundar Vishwanathan

Last Modified Date: 15-Jul-2013


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback