Login
Course Information
Identification

CS 760: Topics in Computational Complexity.
 
Description

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.
 
References

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

https://mrinalkr.bitbucket.io/courses/algebraicmethodS20/algebraicmethodS20.html
 
Prerequisites

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

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback