CS Events Monthly View

Faculty Candidate Talk

Communication Complexity, Quantum Computing and Optimization: New Connections and Insights


Download as iCal file

Monday, February 08, 2021, 10:30am


Speaker: Makrand Sinha


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 between these areas.

Location : Via Zoom

Event Type: Faculty Candidate Talk

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 conjecture due to Rothvoss about optimal linear programs for approximately solving the matching problem. Looking forward, I also propose new directions to explore more connections among these areas with the intention of answering important questions regarding whether quantum speedups need structure, and questions regarding the power of more general optimization approaches, such as semidefinite programming.

Contact  Host: Dr. Mario Szegedy

Join Zoom Meeting

Join by SIP
This email address is being protected from spambots. You need JavaScript enabled to view it.

Meeting ID: 978 2908 6490
Password: 467326
One tap mobile
+12532158782,,97829086490# US (Tacoma)
+13462487799,,97829086490# US (Houston)

Join By Phone
+1 253 215 8782 US (Tacoma)
+1 346 248 7799 US (Houston)
+1 669 900 9128 US (San Jose)
+1 312 626 6799 US (Chicago)
+1 646 558 8656 US (New York)
+1 301 715 8592 US (Washington DC)
Meeting ID: 978 2908 6490
Find your local number: https://rutgers.zoom.us/u/ac1GjtCjhx

Join by Skype for Business