Techniques for Proving Hardness of Problems
Event details
| Date | 18.07.2018 |
| Hour | 10:00 › 12:00 |
| Speaker | Paritosh Garg |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ruediger Urbanke
Thesis advisor: Prof. Ola Svensson
Thesis co-advisor: Prof. Michael Kapralov
Co-examiner: Prof. Michael Gastpar
Abstract
Proving the hardness of problems can give insight where one has failed to design better algorithms with provable guarantees. Not only that, it may give rise to new techniques or extend existing ones which are interesting in its own right.
In recent years, there has been exciting progress in proving unconditional lower bounds for problems in learning theory, communication complexity and sublinear algorithms using techniques from information theory, Fourier analysis and randomness extractors and conditional lower bounds assuming SETH for several classical problems in P. However, there are different variants and models under which these problems remain largely unexplored. This thesis would focus on applying/extending these techniques or developing new ones to prove lower bounds for these problems.
Background papers
Distributed PCP Theorems for Hardness of Approximation in P, by Abboud, A., et al.
Welfare Maximization with Limited Interaction, by Alon, N., et al.
Extractor-Based Time-Space Lower Bounds for Learning, by Garg, S., et al.
Exam president: Prof. Ruediger Urbanke
Thesis advisor: Prof. Ola Svensson
Thesis co-advisor: Prof. Michael Kapralov
Co-examiner: Prof. Michael Gastpar
Abstract
Proving the hardness of problems can give insight where one has failed to design better algorithms with provable guarantees. Not only that, it may give rise to new techniques or extend existing ones which are interesting in its own right.
In recent years, there has been exciting progress in proving unconditional lower bounds for problems in learning theory, communication complexity and sublinear algorithms using techniques from information theory, Fourier analysis and randomness extractors and conditional lower bounds assuming SETH for several classical problems in P. However, there are different variants and models under which these problems remain largely unexplored. This thesis would focus on applying/extending these techniques or developing new ones to prove lower bounds for these problems.
Background papers
Distributed PCP Theorems for Hardness of Approximation in P, by Abboud, A., et al.
Welfare Maximization with Limited Interaction, by Alon, N., et al.
Extractor-Based Time-Space Lower Bounds for Learning, by Garg, S., et al.
Practical information
- General public
- Free
Contact
- EDIC - [email protected]