Requests

To add your request for a presentation of some topic (by other participants):

• username: "ow2018" (no quotation marks)
• password: last name (all lowercase) of the person who discovered matrix multiplication in time $n^{\mathrm{log}_2 7}$
2. click on the edit button in the lower-right corner of this page.
4. save the edited wiki

(Please do not keep the wiki page in edit mode for long, since you may lock other users from editing the text. )

Oded Goldreich: Developments regarding the 2-to-1 game conjecture is the last couple of years. I'd like to see an informative overview of these developments, where by referring to the last couple of years I wish to discourage both a focus on background known to all (e.g., what is PCP) as well as a focus on the last technical breakthrough (i.e., pseudorandom sets in Grassmann graph). [+11 Madhu, Guy, Amnon, Or, Raghu, Salil, Venkat, David, Swastik, Ankit, ryan W]

Muli: I believe the new structural-or-expansion results may have further long term impact, and this is a golden opportunity to discuss this topic. [Oded: In my opinion, this is exactly what a specialized session should offer. In contrast, the plenary presentation should focus on what is currently educational for the community at large, not on what experts should explore in the future.] [Boaz: would be very happy to hear this in such a session]

Oded Goldreich: Circuit Lower Bounds for Nondeterministic Quasi-Polytime. I would like to see an overview of this recent work, but one that does not assume fluency with all prior works leading to it. [+12 Madhu, Amir, Guy, Ron, Raghu, Salil, Rocco, Neeraj, Venkat, David, Boaz, Zvika]

Omer Reingold: Oracle Separation of BQP and PH and any related context. [+6 Amir, Ron, Amnon, David, Ankit, Zvika]

Omer Reingold: High Dimensional Expanders and Applications [+12 Ryan O, Amnon, Salil, Thomas, Raghu, Rocco, Peter, Tselil, David, Swastik, Nikhil, Ankit]

Guy Rothblum: Developments in Code Obfuscation and particularly an overview of recent constructions that use pseudorandom generators with small locality or degree. I'd hope that this could be an accessible overview for the non-cryptographers (I'd also be happy to have a separate followup that can be aimed towards a less-general audience). [+10 Ryan O, Ron, Aviad, Salil, Thomas, Neeraj, David, Raghu, Zvika, ryan W]

Oded Goldreich: Doubly-efficient interactive proof systems. Although Ron did present his work with Guy and Omer in a private session held at the end of our 2015 meeting, I think this work as well as a brief survey of subsequent developments regarding these proof systems does deserve a plenary presentation, allowing all participants to learn of these developments. [+5 Guy, Or, Salil, Swastik, Zvika]

Boaz Barak: I'd love a plenary talk on the recent works on operator scaling. [+8 Ryan O, Amnon, Neeraj, Peter, Tselil, Nikhil, Markus, Christian]

Tselil Schramm: It would also be nice to have a talk (maybe a more specialized followup) about geodesic convexity and geodesic convex optimization more broadly [+1 Rohit].

Boaz Barak: There seem to have been a lot of progress recently in quantum related proof systems, quantum PCP, verifying quantum computation, and other. I would love to hear a talk about this (or perhaps there's even more exciting stuff I'm not aware of in quantum information and computation) [+14 Venkat, Madhu, Ryan O, Guy, Amnon, Aviad, Raghu, Rocco, Salil, Tselil, Nikhil, Ankit, Zvika, ryan W]

Ryan O'Donnell: I'd like to hear about 'No occurrence obstructions in geometric complexity theory'. [+3 Rocco, Neeraj, Ankit]

Ryan O'Donnell: I'd like to hear about matrix multiplication and tensor/Waring rank stuff. [+7 Amnon, Amir, Peter, Tselil, Swastik, Markus, Christian]

Ryan O'Donnell: I'd like to hear about connections between interlacing polynomials, free probability, and random matrices. [+7 Amnon, Raghu, Salil, Thomas, Tselil, Boaz, Ankit]

Ron Rothblum: Hardness of Approximation in Fine Grained Complexity [+3 Salil, Venkat, David]

Venkat Guruswami: FPT and inapproximability (somewhat related to the above theme of fine-grained hardness of approximation)

Venkat Guruswami: Algebraic CSP dichotomy theorem [+1 Boaz]

Amnon Ta-Shma: I'd like to hear about the recent (and exciting!!) developments on PRG against small width branching programs and derandomizing BPL. In particular: [+7 Amir, Or, Salil, Thomas, David, Swastik, Ankit]
- About approximating the inverse of the Laplacian,
- About the BCG (Braverman, Cohen,Garg) approach for liberating the error,
- About the Hoza Zuckerman HSG,
- About the recent developments using the Ajtai-Wigderson framework,
- Perhaps also on the recent suggestion for a PRG against AC^0 with parity.
(Salil: I'm voting to hear about the works on PRGs vs. small-width branching programs, eg Meka-Reingold-Tal and the works leading up to it)
(Thomas: second this, asking also for some context for the relation between these results and what they are getting at)

Madhu Sudan: I'd like to hear about Amnon's results on near-optimal constructions of epsilon-biased sets (and codes!). [+4 Salil, Zvika, Ron, Raghu]

Or Meir: I'd be happy to hear about the work on provable learning algorithm for Markov random fields.

Or Meir: I'd be happy to hear about the works on algorithmic fairness [Guy: I think that recent works developing a complexity-theoretic perspective on this problem, as detailed in Omer Reingold's report, could be especially relevant] [+2 Guy, Ron]

Salil Vadhan: the developments around natural proofs barriers for arithmetic complexity [+2, Peter, Rocco]

Salil Vadhan: the non-rigidity of the Walsh-Hadamard transformation (in a specialized session?) [+3 Venkat, Nikhil Boaz]

Salil Vadhan: improved decoding of algebraic codes (e.g. constant list size for FRS & multiplicity codes) [+2 Raghu, Amnon]

Raghu Meka: Monotone circuit lower bounds from resolution lower bounds and (newish) connections to communication complexity. [+1 Tselil]

Tselil Schramm: I'm curious to hear about L vs RL and progress towards logspace algorithms for undirected ST connectivity [+2 Boaz, Raghu]

Tselil Schramm: I'd also be interested to hear about dimension reduction for matrices as described in the reports of Oded R. and Thomas. [+3 Raghu, Nikhil Boaz]

Zvika B: I'd be happy to hear about the fairly recent proof of the Reverse Minkowski Theorem (and applications). The problem was discussed in a specialized session in the previous meeting. [+1 Raghu]

Ryan Williams: I would like to see an overview of the flurry of recent work on the Minimum Circuit Size Problem / Natural Properties, and the connections to learning and derandomization, such as [Carmosino et al. CCC16, Oliveira and Santhanam CCC17, Impagliazzo, Kabanets, Volkovich CCC18, Oliveira and Santhanam FOCS18, Hirahara FOCS18] [+2 Christian, Raghu]

page revision: 68, last edited: 10 Oct 2018 20:53