Sep 29

NLP Seminar - Alex Tamkin

3:00 PM to 4:00 PM

CS conference room (CSB453)

Alex Tamkin, Stanford University

Sep 30

Decision problems and shallow quantum circuits

10:00 AM to 11:00 AM

CSB 488

Joseph Slote, California Institute of Technology

Abstract: Constant-depth quantum circuits are powerful, capable of solving relational problems that are unconditionally hard for their classical counterparts [e.g., Watts et al. 2019]. It's natural to ask whether a decision separation exists as well, and as a first step in this direction we investigate whether a "QNC0 followed by AC0" hybrid model can approximate the Parity function—a task notoriously hard for AC0 alone.

We find evidence that despite QNC0's apparent power, it does little to help AC0 approximate Parity. In the case of a hybrid with a unitary QNC0 circuit, we give a Fourier-analytic proof that the model does little better than random guessing. To approach the case with a general QNC0 circuit, we reduce to questions about certain nonlocal and non-signaling games, where recent progress on approximate degree bounds [e.g., Sherstov 2018] provide mild no-gos for certain subclasses of AC0. In the interest of a full resolution, we also present work towards a "hybrid switching lemma": we show that non-signaling preprocessing doesn't increase decision tree depth.

Oct 12

NLP Seminar - Violet Peng

3:00 PM to 4:00 PM

CS conference room (CSB453)

Violet Peng, UCLA

Oct 17

Trustworthy Open Source: The Consequences of Success

11:50 AM to 12:40 PM

CSB 451 CS Auditorium

Eric Brewer, Google

Wide-spread use of open-source software is a remarkable achievement, but also creates a tremendous responsibility. How can we collectively step up to ensure open-source software is worthy of the trust the world now expects and deserves? We cover a range of structural and security challenges and how we might address them, including our hopes for a more sustainable future.

Eric is a VP and Fellow at Google and leads technical areas including Kubernetes, Serverless, and Anthos. A recent focus is security for open-source software, including supply-chain risks and helping start the OpenSSF.

At Berkeley, he led work on cloud computing, network infrastructure, IoT, and the CAP Theorem. He has also led work on technology for developing regions, with projects in India, the Philippines, and Kenya among others, including communications, power, and health care.

In 1996, he co-founded Inktomi Corporation and helped lead it onto the NASDAQ 100. In 2000, working with President Clinton, Professor Brewer helped to create, the official portal of the Federal government.

Major awards include membership in the NAE, AAAS, and AAA(&)S, the ACM Prize in Computing, and the ACM SIGOPS Mark Weiser Award.

Oct 19

NLP Seminar - Pamela Mishkin

3:00 PM to 4:00 PM

CS conference room (CSB453)

Pamela Mishkin, OpenAI

Oct 20

Midterm Exams

9:00 AM to 9:00 PM

Nov 28

NLP Seminar - Noemie Elhadad

3:00 PM to 4:00 PM

CS conference room (CSB453)

Noemie Elhadad