Events

Back to Listing

NCSA staff who would like to submit an item for the calendar can email newsdesk@ncsa.illinois.edu.

SPECIAL SEMINAR: Makrand Sinha, "Communication Complexity, Quantum Computing and Optimization: New Connections and Insights"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
Talk and Q&A link will be disseminated via email to limited participants
Virtual
wifi event
Date
Apr 7, 2021   10:00 am  
Contact
Samantha Smith
E-Mail
sdsmith3@illinois.edu
Views
78
Originating Calendar
Computer Science Speakers Calendar

Abstract:

How much information flows through a system? This fundamental question is at the heart of communication complexity. Techniques from this field have turned out to be immensely powerful and fairly universal tools to understand the power of different kinds of algorithms.

 

In this talk, I will describe new methods that I have developed to analyze communication which offer fresh insights into quantum computing and optimization. Using these techniques, I will answer a question of Aaronson and Ambainis regarding the maximal advantage that quantum algorithms can have over classical algorithms in the "blackbox" model, and another question due to Rothvoss about optimal linear programs for approximately solving the matching problem.

 

Looking forward, I also propose new directions to explore further connections among these areas with the intention of answering key questions regarding quantum speedups and more powerful optimization approaches, such as semidefinite programming.

 

 

Bio:

Makrand Sinha is currently a postdoctoral researcher at CWI in Amsterdam hosted by Nikhil Bansal, Ronald de Wolf and Monique Laurent. Prior to that, he obtained his Ph.D. in Computer Science from the University of Washington, Seattle in 2018, under the guidance of Anup Rao. His research interests lie in quantum computing, communication complexity and optimization, and in particular in making connections among these areas.  

 

Faculty Host: Chandra Chekuri

link for robots only