| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 22, 2018 |
| Latest Amendment Date: | May 22, 2018 |
| Award Number: | 1816372 |
| Award Instrument: | Standard Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2018 |
| End Date: | September 30, 2022 (Estimated) |
| Total Intended Award Amount: | $497,239.00 |
| Total Awarded Amount to Date: | $497,239.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
6045 S KENWOOD AVE CHICAGO IL US 60637-2803 (773)834-0409 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
6045 S Kenwood Av Chicago IL US 60637-2803 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Optimization problems arise naturally in many areas such as scheduling, artificial intelligence, software engineering, control of robotic systems, statistics and machine learning. Many of these problems require too long to solve exactly - a common approach for dealing with this has been to design techniques which can efficiently find approximate solutions that are 'good enough' for the task at hand. The study of what approximations are best possible, as well as methods for achieving them, has also led to many new ideas in theoretical computer science, leading to a rich mathematical theory. This project considers several such problems (arising in different areas) which represent challenges to our current understanding. The goal of the project is to develop unified techniques for solving and analyzing them. The project includes several opportunities for training and mentoring of graduate and undergraduate students. Another aim of the project is to develop a collaborative forum for theoretical computer science students in the Chicago area, which can be used to discuss technical ideas and develop expository material.
This project considers various problems in discrete and continuous optimization, which represent bottlenecks for algorithmic techniques for designing approximation algorithms, as well as for techniques proving hardness of approximation. The difficulty of understanding many of these problems arises from the fact that many of them only impose a relatively weak global constraint on the solutions, which is hard to exploit algorithmically and also not amenable to techniques for proving inapproximability. The project considers several continuous optimization problems which offer an ideal testbed for the development of new algorithmic techniques, while still capturing the bottlenecks in proving inapproximability of related discrete problems. The aim of this project is to examine such problems from the following perspectives: (1) average-case hardness and lower bounds for the Sum-of-Squares hierarchy of convex relaxations; (2) techniques and barriers for proving inapproximability; and (3) conditions under which good approximations are achievable.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The goal of this research project was to understand and connect techniques for arguing about the approximability of discrete and continuous optimization problems, and to develop new algorithmic and analytic methods to reason about a variety of optimization problems, where current approximation algorithms seem to face a bottleneck. The project led to the following research outcomes:
- A unified framework for understanding the approximability of operator norms. Computing or approximating norms of operators mapping one normed space to another represents a fundamental class of continuous optimization problems, with connections to several problems in discrete optimization. The project led to the first NP-hardness lower bounds for approximability of the so-called "hypercontractive norms" and also new framework capturing previously known upper and lower bounds in other cases.
- An understanding of novel forms of expansion in discrete structures, and their role in analyzying convex optimization algorithms based on semidefinite programming. The work done as part of this project led to new algorithms, as well as new lower bounds, for the approximation of Constraint Satisfaction Problems (CSPs). Moreover, it led to new structural understanding of how various "expansion" properties of the underlying problem instances can play a role in the analysis of approximation algorithms based on semidefinite programming.
- New algorithms for decoding novel families of codes. The research done as part of this project established new connections between the algorithmic problem of decoding certain families of error-correcting codes, and that of approximately solving CSPs. Moreover, using connections of CSPs to expansion developed above, and the expansion properties of code families, it led to new algorithmic techniques for decoding such codes.
- New techniques for analyzing random matrices arising in the analysis of spectral and semidefinite optimization algorithms. The project helped develop new methods to understand concentration behavior of random matrices with dependent random entries, motivated by the analysis of several spectral and optimization algorithms. The research done as part of the project helped develop a unified framework for analyzing a large family of such random matrices, and hence also the algorithms relying on their spectral properties.
Other than the research results described above, the project also provided training opportunities for several graduate students who participated in the above research projects, with the above research forming a signification part of their dissertations. Several of the relevant topics for this project were also studied and discussed in reading groups, which helped develop a better understanding of the content for students at TTIC and the University of Chicago. The research results from the project, notes from some of the reading groups, as well as notes and videos from courses taught by the PI, have all been made publicly available. While supported by this award, the PI also helped start a new online summer school called "New Horizons in TCS" which the PI has been co-organizing for the past two years. This summer-school is aimed at providing an exposure to research in various areas in, and related to, theoretical computer science (TCS). The summer school particularly encourages applications from minorities currently under-represented in TCS, and aims to broaden the participation in TCS research.
Last Modified: 04/30/2023
Modified by: Madhur Tulsiani
Please report errors in award information by writing to: awardsearch@nsf.gov.
