| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | December 7, 2011 |
| Latest Amendment Date: | March 4, 2016 |
| Award Number: | 1149018 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Dmitri Maslov
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | June 1, 2012 |
| End Date: | May 31, 2018 (Estimated) |
| Total Intended Award Amount: | $499,995.00 |
| Total Awarded Amount to Date: | $499,995.00 |
| Funds Obligated to Date: |
FY 2013 = $95,247.00 FY 2014 = $99,271.00 FY 2015 = $104,136.00 FY 2016 = $109,067.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
10889 WILSHIRE BLVD STE 700 LOS ANGELES CA US 90024-4200 (310)794-0102 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
4732 Boelter Hall Los Angeles CA US 90095-1596 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01001314DB NSF RESEARCH & RELATED ACTIVIT 01001415DB NSF RESEARCH & RELATED ACTIVIT 01001516DB NSF RESEARCH & RELATED ACTIVIT 01001617DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Consider a function whose arguments are distributed among several parties, making it impossible for any one party to compute it in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate the function. Pioneered by Andrew Yao over thirty years ago, communication complexity has become a central research area in theoretical computer science. First of all, studying communication as a limited resource has a strong practical motivation. Moreover, open problems in many other computational models reduce to questions about communication. To date, communication complexity theory has impacted almost every subject in theoretical computer science, from classical models such as Turing machines and circuits to more recent topics such as data structures, learning theory, and quantum computing.
This award takes aim at studying three longstanding open questions in communication complexity theory: (i) the limits of multiparty communication; (ii) the limits of communication with alternating existential and universal quantifiers; (iii) the conjectured equivalence of the combinatorial and matrix-theoretic views of communication. A resolution of these questions would have major consequences in theoretical computer science beyond communication, including lower bounds for ACC circuits and neural networks, efficient learning of DNF formulas, and an equivalence of quantum and classical communication.
Progress on the proposed problems will exploit insights from, and contribute new ideas to, other disciplines such as machine learning and matrix theory. This award provides an ample source of research problems at various levels of difficulty and will be used in advising students and teaching new graduate and undergraduate courses. As an integral part of the award, the PI will promote theory research in the Los Angeles area and take an active part in scientific dissemination.
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.
Intellectual merit
Communication complexity theory studies the minimum amount of communication, measured in bits, required in order to compute functions whose arguments are distributed among several parties. In addition to the basic importance of studying communication as a bottleneck resource, the theory has a vast number of applications in theoretical computer science and beyond. As the research component of this project, the investigator solved a number of significant open problems in communication complexity theory and related areas. This project produced 9 publications at STOC and FOCS, the most selective conferences in theoretical computer science. Four of these publications were additionally honored with an invitation to appear in special issues of the SIAM Journal on Computing for top STOC and FOCS papers. The investigator's results on communication complexity include:
- a near-optimal lower bound on the multiparty communication requirements of the set disjointness problem, which plays a central role in the area;
- an optimal method for simulating any two-party communication protocol over a channel that is subject to adversarial insertions, deletions, and substitutions;
- an optimal method for compressing any two-party communication protocol to its information content whenever the participants' inputs are independent random variables, complementing known impossibility results for dependent inputs.
In addition, the investigator solved several well-known open problems on the approximation of Boolean functions by real polynomials, with applications to communication complexity, computational learning, and quantum computing. The investigator's results include:
- an optimal method for making any bounded multivariate polynomial robust to noise in the inputs with only a constant-factor increase in degree, which solves a 10-year-old problem;
- a strong lower bound on the polynomial degree required to sign-represent constant-depth circuits, which improves on 45 years' worth of research and settles an 11-year-old conjecture;
- a novel, first-principles approach for constructing approximating polynomials for key problems, matching or improving on the performance of the previous (vastly more complicated) approach based on quantum algorithms;
- determination of the polynomial degree required to pointwise approximate any depth-2 AND-OR tree, which closes a 19-year line of work.
Broader impacts
As an integral part of this project, the investigator designed and taught at UCLA an undergraduate course (CS 181 "Formal Languages and Automata Theory") and two graduate courses (CS 289 "Communication Complexity" and CS 281 "Computability and Complexity"). The undergraduate course, required of all CS and CSE majors at UCLA, provides training in formal proof and introduces such fundamental notions as algorithms, efficiency, reductions, and undecidability. The two graduate courses serve a diverse group of Ph.D. and Masters students, with diverse skill sets, academic backgrounds, and thesis areas, from the departments of Computer Science, Mathematics, and Electrical Engineering. The investigator designed his courses from scratch according to his own pedagogical aesthetics, in each case substantially reworking the presentation in the accompanying textbook and research literature. Except for an occasional quarter off teaching, the investigator taught each of these courses once a year since 2012, varying the topic selection in each graduate offering.
The student response has been extraordinary. The investigator consistently receives near-perfect ratings in all categories (instructor concern, lecture preparation, helpfulness, communication skills, course material, overall instructor rating, overall course rating). A 2017 article in UCLA's Daily Bruin reports that the investigator's undergraduate course (CS 181) has the third highest rating of all courses campus-wide. The investigator is the winner of the 2014 Northrop Grumman Excellence in Teaching Award, among all faculty in UCLA's School of Engineering, and was nominated last year for UCLA's Campus-Wide Distinguished Teaching Award. Recently, the investigator shared his pedagogical innovations as an invited speaker at a workshop organized by UCLA's School of Engineering.
In addition to contributing to the development of human resources through teaching, the investigator has served on the Ph.D. and Masters committees of 25+ graduate students in the departments of Computer Science, Mathematics, and Electrical Engineering, bringing his research perspective to other research groups at UCLA and encouraging cross-disciplinary thought. The investigator is also the faculty advisor of 35 undergraduate students and meets with them on a regular basis to guide them in any academic matter and help with their internship and job search.
The investigator is committed to the broadest possible dissemination of his research and pedagogical contributions. The investigator maintains up-to-date electronic versions of all his research papers on his web page, and likewise for all his pedagogical products. The investigator frequently gives invited talks on his research and also takes every opportunity to reach nonresearch audiences, including a talk at UCLA's Annual Engineering Tech Forum (2013) and a talk at the investigator's alma mater Hope College (2015), an undergraduate-only liberal arts institution. As part of this project, the investigator authored an invited research survey on the set disjointness problem. The investigator is a supporter of low-cost and open-access publishing and regularly publishes in Theory of Computing, a selective open-access journal.
Last Modified: 06/07/2018
Modified by: Alexander A Sherstov
Please report errors in award information by writing to: awardsearch@nsf.gov.
