Requests

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

• 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: Update on the recent two-source extractors.
(Seconded by O'Donnell, Barak, Ron Rothblum, Meka, Cohen, Tan, Shpilka, ZB, Shafi, Venkat, Christina, Vinod, Saks)

Oded Goldreich: The two-server PIR of Zeev Dvir (and Sivakanth Gopi)
(Seconded by Tan, ZB, Dinur, Zuckerman, Christina, Gillat)

Oded Goldreich: Update on Parallel Repetition, possibly by Irit
(Seconded by Cohen, Forbes, Christina).

Madhu Sudan: Recent progress on LDCs and LTCs by Or Meir and co.
Supported by OdedG, Ron Rothblum, Cohen, Chattopadhyay, Zuckerman.

Ryan O'Donnell: GCT and permanent vs. determinant news; e.g., Ikenmeyer--Mulmuley--Walter and Landsberg--Ressayre
(Seconded by Meir, Barak, Servedio, Tan, Bläser, Shafi, Forbes, Burgisser, Vinod)

Ryan O'Donnell: SOS lower bounds for Clique (Meka — Potechin — Wigderson, Deshpande — Montanari, Hopkins — Kothari — Potechin, Raghavendra — Schramm), and pairwise independent CSPs (Barak — Chan — Kothari)
(Seconded by Razborov, Christina, Saks)

Ryan O'Donnell: query complexity breakthroughs of Göös — Pitassi — Watson, Ambainis — Balodis — Belovs — Lee — Santha — Smotrovs, Mukhopadhyay — Sanyal, Ben-David
(seconded by Barak, Meka, Cohen, Servedio, Tan, Shpilka, Chattopadhyay, Razborov, ZB, Avi, Shafi, Forbes, Venkat, Zuckerman, Vinod; added by Venkat: may be it is appropriate to have two talks in this thread, one focused on communication complexity and another on query complexity (randomized, quantum, etc.)?)

Ryan O'Donnell: latest developments in random k-SAT and the statistical physics perspective; e.g., the Ding--Sly--Sun threshold theorem and the Marino--Parisi--Ricci-Tersenghi 3Sat algorithm that seemingly works up to the threshold
(seconded by Barak - especially the Marino-Parisi-Ricci-Tersenghi one, Servedio, Tan, Avi, Shafi, Vinod, Saks)

Salil Vadhan: the Marcus-Spielman-Srivistava proof (and/or follow-ups) of the existence of Ramanujan graphs of all degrees, if anyone has developed a good understanding/intuition it
(seconded by Barak, Meka, Cohen, Servedio, Tan, Shpilka, Chattopadhyay, Burgisser)

Zvika Brakerski: Recent developments in quantum/classical algorithms for finding short generators in principle ideals (by Oded R?).
(seconded by Barak, Razborov, Forbes, Blömer, Burgisser, Vinod)

Michael Forbes: Recent AC^0 lower bounds by Rossman, Tan, Servedio
(seconded by Ron Rothblum, Cohen, Meir, and Meka, Shpilka, Chattopadhyay, Bläser, Blömer, Christina,Saks)

Mark Braverman: An update on the complexity assumptions needed to fuel recent cryptography advances (FHE, obfuscation).
Supported by OdedG, Shpilka (seconded by Barak - also would be interested to know if the algorithms Zvika mentions have any bearings on this), (seconded by Meka - a survey of the results would also be great), Shafi, Zuckerman, Christina, Gillat

Boaz Barak: If someone knows enough about Tao's recent resolution of the Erdos discrepancy problem I'd love to hear about it
(Seconded by Cohen, Chattopadhyay, Avi, Zuckerman, Saks)

Raghu Meka: Theory behind/in natural language processing problems such as this paper of Arora, Li, Liang, Ma, and Risteski.
(Seconded by Meir, Dinur, Blömer, Gillat)

Or Meir: An update about recent progress on small-space derandomization
(seconded by Shpilka, Chattopadhyay, Bläser, Zuckerman, Christina,Saks).

Avi Wigderson: Update on the breakthrough results in achieving capacity in constant rate Reed-Muller codes over BEC by Pfister and Kumar.
(earlier this year we did that for rates near 0 and 1 with Amir Shpilka and Emmanuel Abbe). I would volunteer Amir Shpilka to give this talk :)
(seconded by Christina, Zuckerman)

Avi Wigderson: I can talk about many connections from Invariant Theory, Quantum Information Theory, Non-commutative algebra and Optimization that motivate, and eventually solve a non-commutative variant of the PIT problem. There is a lot of background material, so I anyway plan to offer a 2 hour evening talk on this. (supported by Shpilka and Regev, Burgisser, Zuckerman,Saks)

Madhu Sudan: Separation of bounded depth polysize formulae from bounded-depth polysize circuits by Ben Rossman. (seconded by Shpilka, Venkat, Burgisser, Zuckerman, Christina)

Shafi: Update on Recent results on connecting advances on conditional lower bounds for algorithms such as 3SUM, Boolean Matrix Multiplication etc based on complexity theory conjectures. Seems a must. (seconded by Venkat: connections to parameterized complexity would also be great to hear, either as part of this, or separately as an update on some key developments; seconded by Vinod, Gillat)

Shafi: Update (if anyone can do it) on advances in Stochastic Block Modeling (seconded by Venkat, may be as part of a bigger picture on matching information-theoretic thresholds with efficient algorithms, or evidence that this may be hard in some settings?)

Salil: If anyone can do it, the recent hardness results for (improper) PAC learning, eg of DNF formulas, by Amit Daniely, Shai Shalev-Schwartz, Nati Linial (STOC 2014 and follow-ups). (seconded by Dinur, ZB, Blömer, Christina,Saks,Gillat)

Venkat Guruswami: Update on codes for distributed storage (locally recoverable, maximally recoverable, regenerating, etc.), and recent progress on field size lower bounds for some topologies/forbidden subgraphs (by Guangda Hu et al?, if it will be public soon); may be by Parikshit? (Seconded by Zuckerman)

Venkat Guruswami: sort of dual to Shafi's request above, improvements in algorithm runtimes for core problems using the polynomial method (by Ryan Williams)

Venkat: Update/survey on indistinguishability obfuscation and its connections to other crypto primitives. (Zuckerman: I support this, but I think this is already what Braverman suggests above. Christina: I support this and think that it is different from Braverman's suggestion, applications rather than assumptions. Vinod might be able to do this, also including applications of approximate obfuscation which potentially has applications on the key agreement from one-way function question. Vinod: I am happy to do this.)

Venkat Guruswami: I can talk about polar codes, mostly a survey of Arikan's work, but touching upon their complexity benefits in achieving Shannon capacity, and basic entropic questions that arise in their analysis (these have an additive combinatorics flavor, as described here). (Seconded by Zuckerman, Shpilka)

Oded Regev: I can talk about a recent conjecture on the geometry of lattices that arose from complexity work and the surprising number of applications we have for them (seconded by Vinod: is this the Kannan-Lovasz conjecture?)

page revision: 73, last edited: 01 Nov 2015 07:06