my choices [Oded Goldreich, started 2009]

Go to the most recent choice.

Preface

FAQ: but most of your choices have appeared in STOC/FOCS. See my answer

Warning and request: Unfortunately, my comments contain lots of typos and various other errors. Please don't hesitate calling my attention to such cases.

[Editorial decisions.]
Initial policy: Include only works that I heard or read after Jan. 1, 2009.
Feb. 22, 2009: Include also surveys (see the 1st such case).
Mar. 8, 2009: Include "double features" (see the 1st such case).
Jul. 10, 2009: Include also highlights on open problems (see the 1st such case).
Jan. 15, 2010: Include also overall accounts of workshops and/or conferences (see the 1st such case).
March 2010: Revising the web-page format - moving my comments (and the original abstracts) to separate pages. [See old version.]
May 16, 2012: Include also useful observations decoupled from the work in which they appear (see the 1st such case).
July 26, 2012: Include also old ideas that I regret not having known before (see the 1st such case).
March 28, 2013: Adding general terms.
Sept 9, 2013: Annotating the RSS items (starting from Nr. 137).

Legend for General Terms (indicated in the choice's time+location line): CRY = Cryptography, CT = Complexity Theory, EXT = (Randomness) Extractors, PPS = Probabilistic Proof Systems, PRG = Pseudorandomness, PT = Property Testing, RnC = Randomness and Computation. I tried to pick only one term per entry, although there is an obvious overlap between these terms.

[Omer at Shafi's Seminar, Jan. 22, 2009] (PRG)
Accessible Entropy (tentative title) by Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee.
See my comments and the original abstract

[Ran in the WIS Theory Seminar, Feb. 1, 2009] (PPS)
A Counterexample to Strong Parallel Repetition by Ran Raz
See my comments and the original abstract

[Kobbi at Shafi's Seminar, Feb. 5, 2009] (CRY)
What Can We Learn Privately? by Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.
See my comments and the original abstract

[Private presentation by Or Meir, Feb. 12, 2009] (Avi: "Shame on you, did you not know it?") (CT)
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized by Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson
See my comments and the original abstract

[Dieter at the WIS Theory Seminar, Feb. 22, 2009] (CT)
Lower Bounds for Satisfiability and Related Problems (a survey) by Dieter van Melkebeek
See my comments and the original abstract

[Avi at the WIS Theory Seminar, March 8, 2009] [+ recall of a private presentation by Elazar, Dec. 25th 2008] (CT)
(1) Locally Testing Direct Product in the Low Error Range by Irit Dinur and Elazar Goldenberg
(2) New Direct Product Code Testers, and PCPs by Valentine Kabanets, Russell Impagliazzo, and Avi Wigderson
See my comments and the abstract of Avi's talk

[Tal at TCC'09, March 15, 2009] (CRY)
An Optimally Fair Coin Toss by Tal Moran, Moni Naor, and Gil Segev.
See my comments and the original abstract

[Krzysztof at Weizmann's Theory Seminar, Mar. 22, 2009] (RnC)
Sublinear Graph Approximation Algorithms by Krzysztof Onak, based on joint works with Noga Alon, Avinatan Hassidim, Jonathan A. Kelner, Philip N. Klein, and Huy N. Nguyen.
See my comments and the talk's abstract

[Klim at the WIS Theory Seminar, Mar. 29, 2009] (RnC)
3-Query Locally Decodable Codes of Subexponential Length by Klim Efremenko
See my comments and the original abstract

[Iftach, private discussion, March 2009] (PPS)
A Parallel Repetition Theorem for Any Interactive Argument by Iftach Haitner
See my comments and the original abstract

[reading, March 2009] (PPS)
Are PCPs Inherent in Efficient Arguments? by Guy Rothblum and Salil Vadhan
See my comments and the original abstract

[reading, March 2009] (CT)
Worst-Case Running Times for Average-Case Algorithms by L. Antunes and L. Fortnow
See my comments and the original abstract

[reading + private discussions with the authors, April 2009] (PPS)
Composition of low-error 2-query PCPs using decodable PCPs by Irit Dinur and Prahladh Harsha
See my comments and the original abstract

[presentation in Eurocrypt'09, Apr. 27, 2009] (CRY) [+ a recall from announcement at TCC'09, Mar. 16, 2007]
Two recent works on resettable security by Vipul Goyal and Amit Sahai:
(1) Resettably Secure Computation, presented at Eurocrypt'09.
(2) Resolving the simultaneous Resettability Conjecture, announced at the rump session of TCC'09.
See my comments and the original abstracts

[email exchange with Rafail, May 2009; following announcement at TCC'09] (CRY)
Two recent works justifying various features of known zero-knowledge protocols.
(1) On the Composition of Public-Coin Zero-Knowledge Protocols, by Rafael Pass, Wei-Lung Dustin Tseng, and Douglas Wikstrum.
(2) On Public versus Private Coins in Zero-knowledge Proof Systems, by Rafael Pass and Muthuramakrishnan Venkitasubramaniam.
See my comments and the original abstracts

[Per at STOC'09, June 1, 2009] (CT)
Randomly supported independence and resistance by Per Austrin and Johan Hastad
See my comments and the original abstract

[talk at STOC'09, June 1, 2009] (RnC)
Twice-Ramanujan Sparsifiers by Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava
See my comments and the original abstract

[two talks at STOC'09, May 31, 2009] (CRY)
Two related works on non-malleable commitments (NMCs).
(1) Non-Malleability Amplification by Huijia Lin and Rafael Pass
(2) A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability by Huijia Lin and Rafael Pass and Muthuramakrishnan Venkitasubramaniam
See my comments and the original abstracts

[Eric at STOC'09, May 31, 2009] (PT)
Testing Juntas Nearly Optimally by Eric Blais
See my comments and the original abstract

[July 10, 2009] (EXT)
Efficient Two-Sources Randomness Extraction: A Challenge from the mid-1980s
See my comments

[Youming at Random'09, Aug. 21, 2009] (CT)
On the Security of Goldreich's One-Way Function by Andrej Bogdanov and Youming Qiao.
See my comments and the original abstract

[Shachar at Random'09, Aug. 21, 2009] (CT)
Random low degree polynomials are hard to approximate by Ido Ben Eliezer, Rani Hod and Shachar Lovett.
See my comments and the original abstract

[Jeff at Random'09, Aug. 23, 2009] (CT)
Pseudorandom Generators and Typically-Correct Derandomization by Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel.
See my comments and the original abstract

[Nina at the Barriers in Computational Complexity workshop, Aug. 28, 2009]. (RnC)
Approximate Clustering without the Approximation by Maria-Florina (Nina) Balcan [Based mainly on works with Avrim Blum, Anupam Gupta, and Santosh Vempala]
See my comments and the original abstract

[Eden at the WIS theory Seminar, Nov. 8, 2009]
New Approximation Algorithms for Densest k-Subgraph (RnC) by Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige and Aravindan Vijayaraghavan.
See my comments and the original abstract

[Amir at MFO, Nov. 16, 2009] (CT)
Update on Polynomial Identity Testing by Amir Shpilka.
See my comments and the original abstract

[Zeev at MFO, Nov. 17, 2009] (EXT)
Kakeya Sets and Extractors (survey) by Zeev Dvir.
See my comments and the original abstract

[Les at MFO, Nov. 17, 2009] (CT)
Holographic Algorithms by Leslie Valiant.
See my comments and the original abstract

[Anup at MFO, Nov. 17, 2009] (CT)
Direct Sums in Randomized Communication Complexity by Boaz Barak, Mark Braverman, Anup Rao and Xi Chen.
See my comments and the original abstract

[Chris at MFO, Nov. 18, 2009] (RnC)
Fast polynomial factorization and modular composition by Kiran Kedlaya and Chris Umans
See my comments and the original abstract

[Omer at MFO, Nov. 18, 2009] (PRG)
Going down HILL: Efficiency Improvements for Constructions of PRG from any OWF by Iftach Haitner, Omer Reingold and Salil Vadhan.
See my comments and the original abstract

[Prasad at MFO, Nov. 19, 2009] (CT)
Complexity of CSPs: Exact and Approximation by Prasad Raghavendra.
See my comments and the original abstract

[Ben at MFO, Nov. 20, 2009] (CT)
k-Clique on Random Graphs by Ben Rossman.
See my comments and the original abstract

[Mark at MFO, Nov. 20, 2009] (PRG)
Poly-logarithmic independence fools AC0 circuits by Mark Braverman.
See my comments and the original abstract

[Scott at MFO, Nov. 20, 2009] (CT)
Efficient Simulation of Quantum Mechanics Collapses the Polynomial Hierarchy by Scott Aaronson.
See my comments and the original abstract

[Shiri at the WIS Theory Seminar, Nov. 22, 2009] (RnC)
Fault-Tolerant Spanners for General Graphs by Shiri Chechik, Michael Langberg, David Peleg and Liam Roditty.
See my comments and the original abstract

[Benny at the WIS Theory Seminar, Dec. 6, 2009] (PRG)
Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature? by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz.
See my comments and the original abstract

[ITCS, Tsinghua University, Beijing, Jan. 8-10, 2010] (PT)
The ITCS mini-workshop on Property Testing, January 2010
See the workshop's abstract and an annotated program of the workshop. The following three choices are taken from this program.

[Rocco at the ITCS mini-workshop on Property Testing, Jan. 8, 2010] (PT)
Testing by Implicit Learning (survey) by Rocco Servedio.
See my comments and the original abstract

[Madhu at the ITCS mini-workshop on Property Testing, Jan. 9, 2010] (PT)
Invariance in Property testing (survey) by Madhu Sudan.
See my comments and the original abstract

[Shubhangi at the ITCS mini-workshop on Property Testing, Jan. 10, 2010] (PT)
Some recent results on testing of sparse linear codes by Swastik Kopparty and Shubhangi Saraf.
See my comments and the original abstract

[ETH, Zurich, Feb. 9-11, 2010] (CRY)
The 7th Theory of Cryptography Conference (TCC), February 2010
See my notes regarding ten talks presented in this conference (see list).

[private presentation of Zvika (Brakerski), Mar. 14, 2010] (CRY)
Two related works on Oblivious RAMs:
(1) Oblivious RAMs without Cryptographic Assumptions by Ajtai.
(2) Perfectly Secure Oblivious RAM Without Random Oracles by Damgard, Meldgaard, and Nielsen.
See my comments and the original abstracts

[scanning the FOCS'09 proceedings, March 2010] (better late than never.) (RnC)
Needless to say, the following works are unrelated.
(1) Faster Generation of Random Spanning Trees by Jonathan A. Kelner and Aleksander Madry.
(2) Constructing Small-Bias Sets from Algebraic-Geometric Codes by Avraham Ben-Aroya and Amnon Ta-Shma.
(3) A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems by Falk Unger.
(4) A Complete Characterization of Statistical Query Learning with Applications to Evolvability by Vitaly Feldman.
Note: a handful of other works are covered by previous choices.
See my comments

[Or at WIS's Theory Seminar, March 28, 2010] (PPS)
Derandomized Parallel Repetition of Structured PCPs by Irit Dinur and Or Meir
See my comments and the original abstract

[Private presentation by Benny, April 25, 2010] (CRY)
Public-Key Encryption Schemes from Different Assumptions by Benny Applebaum, Boaz Barak and Avi Wigderson.
See my comments and the original abstract

[Moni at the MTA lecture in memory of Shimon Even, May 5, 2010] (RnC)
Cuckoo Nesting: Modern Methods for Organizing Lookup Tables. by Moni Naor.
See my comments

[reading ECCC's TR10-072, May 2010] (RnC)
Constructive Proofs of Concentration Bounds by Russell Impagliazzo and Valentine Kabanets.
See my comments

[Allan at a conference marking Joachim von zur Gathen's 60th birthday, May 28, 2010] (CT)
Greedy algorithms and why simple algorithms can be complex by Allan Borodin
See my comments

[Email exposition by Mohammad, May 31, 2010] (CT)
On the Power of Randomized Reductions and the Checkability of SAT by Mohammad Mahmoody and David Xiao
See my comments

[Reading from the CCC'10 proceedings, June 23, 2010] (CT)
The program-enumeration bottleneck in average-case complexity theory by Luca Trevisan
See my comments

[Expositions by Or (+ reading a draft of the paper), Aug. 29, 2010] (PPS)
IP = PSPACE using Error Correcting Codes by Or Meir
See my comments

[Dana at RANDOM'10, Sept. 1, 2010] (PT)
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries by Elya Dolev and Dana Ron.
See my comments

[Recommended by Madhu, Sept. 24, 2010] [Swastik at the WIS Theory Seminar, July 11, 2011] (RnC)
High-rate codes with sublinear-time decoding by Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin.
See my comments

[Recommended by Avi, Oct. 5, 2010] (CT)
NP-Hardness of Approximately Solving Linear Equations Over Reals by Subhash Khot and Dana Moshkovitz.
See my comments

[Scanning FOCS'10 papers, Oct. 28, 2010] (CT)
The complexity of distributions by Emanuele Viola
See my comments

[Private presentations by Or Meir, Nov. 2010] (CT)
Two papers by Ryan Williams
(1) Improving Exhaustive Search Implies Superpolynomial Lower Bounds
(2) Non-Uniform ACC Circuit Lower Bounds
See my comments, which is the main resason for posting a choice of this celebrated entry.

[Shai in the Weizmann theory seminar, Nov. 15, 2010] (CRY)
Fully Homomorphic Encryption over the Integers by Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan.
See my comments and original abstract

[Yuri in the Weizmann theory seminar, Nov. 29, 2010] (RnC)
Triangular Rank and Dimension Reduction for $L_1$ Metrics by Ilan Newman and Yuri Rabinovich
See my comments and original abstract

[Artur in the Weizmann theory seminar, Dec. 6, 2010] (PT)
Testing properties in arbitrary planar graphs via random walks by Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler.
See my comments and original abstract

[ECCC posting, Nov. 2010] (PT)
Two related papers by Gregory Valiant and Paul Valiant: (1) A CLT and tight lower bounds for estimating entropy (2) Estimating the unseen: A sublinear-sample canonical estimator of distributions
See my comments and original abstract

[Guy in the Weizmann theory seminar, Dec. 19, 2010] (CRY)
Boosting and Differential Privacy by Cynthia Dwork, Guy Rothblum, and Salil Vadhan.
See my comments and original abstract

[Benny in the Weizmann theory seminar, Jan. 24, 2011] (Indeed, I got some previews, months ago.) (PRG)
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions by Benny Applebaum
See my comments and original abstract

[Foundations and Trends in TCS, Vol.~5, Issue 3-4, 2010] (CT)
Arithmetic Circuits: A survey of recent results and open questions by Amir Shpilka and Amir Yehudayoff
See my comments and original abstract

[Feb 21, 2011]
Open Problem: Good Locally Testable Codes - constant in all parameters (PT)
See my comments

[Found on the web, Mar. 2, 2011] (PT)
Property Testing Lower Bounds Via Communication Complexity by Eric Blais, Joshua Brody, and Kevin Matulef
See my comments and original abstract

[From ECCC, Mar. 17, 2011]
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation (CRY) by Gilad Asharov and Yehuda Lindell
See my comments and original abstract

[IHP, Paris, Mar. 25, 2011] (RnC)
Expander graphs: applications and constructions (a mini-course of 3 lectures) by Avi Wigderson
See my comments and pointer to slides

[Private presentation by Guy, Mar. 27, 2011] (CRY)
A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis by Moritz Hardt and Guy Rothblum
See my comments and the original abstract

[Brown U., March 28-30, 2011] (CRY)
Comments on Fifteen TCC'11 Presentations (LNCS 6597)
See my comments

[Shiri Chechik in the Weizmann theory group meeting, May 11, 2011]
Subcubic Equivalences Between Path, Matrix, and Triangle Problems by Virginia Vassilevska Williams and Ryan Williams
See my comments

[Bertinoro, May 23-27, 2011] (PT)
Highlights of the Bertinoro Workshop on Sublinear Algorithms (see workshop's webpage):
* Optimal O(1)-time approximations of bounded-degree CSPs by Yuichi Yoshida
* Learning and testing k-modal distributions by Rocco Servedio (et al)
These two talks as well as twenty additional ones are briefly reviewed in my comments

[Avi in the Weizmann theory of computation seminar, June 6, 2011] (CT)
Determinant and Permanent (a survey talk) by Avi Wigderson
See my comments

[Zvika in the Weizmann theory of computation seminar, June 15, 2011] (CRY)
Efficient Fully Homomorphic Encryption from (Standard) LWE by Zvika Brakerski and Vinod Vaikuntanathan.
See my comments

[Prahladh in the Weizmann theory of computation seminar, June 20, 2011] (CT)
Almost Settling the Hardness of Noncommutative Determinant by Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan
See my comments

[Omer in the Weizmann theory of computation lunch, June 22, 2011] (RnC)
Balls and Bins: Smaller Hash Families and Faster Evaluation by Laura Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder
See my comments

[Princeton U., August 17-19, 2011] (RnC)
On fourteen RANDOM/APPROX'11 Presentations (cf LNCS 6845)
See my comments

[Reading on ECCC, Sept 29, 2011] (PT)
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy by Madhav Jha and Sofya Raskhodnikova
See my comments

[Recalling a discussion with Benny, Oct 12, 2011] (PRG)
A Dichotomy for Local Small-Bias Generators by Benny Applebaum, Andrej Bogdanov, and Alon Rosen
See my comments

[Recalling a discussion with Shafi, Oct 12, 2011] (RnC)
Probabilistic Search Algorithms and their Cryptographic Applications by Eran Gat and Shafi Goldwasser
See my comments

[Found on ECCC, Nov 2, 2011] (PRG)
Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions by Salil Vadhan and Colin Jia Zheng
See my comments

[NYC Theory day, Nov 11, 2011] (RnC)
Entropy-based Bounds on Dimension Reduction in L1 by Oded Regev
See my comments

[Seminar announcement in UCB, Nov 28, 2011] (CT)
Breaking the Coppersmith-Winograd Barrier by Virginia Vassilevska Williams
See my comments

[Seen on ECCC, Dec 7, 2011] (CT)
Restriction Access by Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff
See my comments

[Private presentation by Avi W., Feb 15, 2012] (RnC)
High-Confidence Predictions under Adversarial Uncertainty by Andrew Drucker
See my comments

[TCC'12, March 19-21, 2012] (CRY)
Open Problems and Useful Observations by various speakers at TCC'12
See my comments

[April 2, 2012] (PRG)
Approximating the Number of Satisfying Assignments in DNFs: A Derandomization Challenge from the early-1990s
See my comments

[Seen on ECCC, TR12-034, April 9, 2012] (RnC)
New Lower Bounds for Matching Vector Codes by Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett.
See my comments

[Seen on ECCC, TR12-026, April 15, 2012] (CT)
Time Hierarchies for Sampling Distributions by Thomas Watson
See my comments

[Seen on ECCC, TR12-043, April 20, 2012] (RnC)
Efficient Interactive Coding Against Adversarial Noise by Zvika Brakerski and Yael Tauman Kalai
See my comments

[NYC Theory day, May 4, 2012]
Four talks at NYC Theory day by Michael Kearns (on Experiments in Social Computation), Eli Ben-Sasson (on An Additive Combinatorics Approach to the Log-rank Conjecture), Aleksander Madry (on Online Algorithms and the K-server Conjecture), and Shubhangi Saraf (on The Method of Multiplicities).
See my comments

[A late notice of ECCC TR10-144, May 5, 2012] (EXT)
From Affine to Two-Source Extractors via Approximate Duality by Eli Ben-Sasson and Noga Zewi
See my comments

[Seen on ECCC, TR12-060, May 15, 2012] (PRG)
DNF Sparsification and a Faster Deterministic Counting by Parikshit Gopalan, Raghu Meka, and Omer Reingold
See my comments

[Referred to by Or, May 2012] (PPS)
An observation regarding the construction of practical probabilistic proof systems taken from the work On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs by Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer (ECCC TR12-045).
See my comments

[Heard in STOC'12, May 20, 2012] (CT)
Two works regarding the Unique Games (UG) Conjecture
(1) A new point of NP-hardness for Unique Games by Ryan O'Donnell, John Wright
(2) Hypercontractivity, Sum-of-Squares Proofs, and their Applications by Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
See my comments

[Missed in STOC'12, found on ECCC; May 21, 2012] (CT)
Interactive Information Complexity by Mark Braverman.
See my comments

[Heard in STOC'12, May 21, 2012]
Three exciting algorithmic works
(1) Routing in Undirected Graphs with Constant Congestion by Julia Chuzhoy
(2) Improving Chrisofides' Algorithm for the s-t Path TSP by Hyung-Chan An, Robert Kleinberg, David B. Shmoys
(3) Multiplying Matrices Faster Than Coppersmith-Winograd by Virginia Vassilevska Williams
See my comments

[Referred to by Or, June 20th, 2012] (PRG)
Pseudorandomness from Shrinkage by Russell Impagliazzo, Raghu Meka, and David Zuckerman
See my comments, which offer a restricted perspective on their work; referring to the (in)sensitivity of some ``space fooling'' PRGs to the order in which their output bits are presented (the current work that refers top the Nisan-Zuckerman PRG is constrasted with known results regarding Nisan's PRG).

[In CCC'12, referred to by Or, July 7th, 2012] (RnC)
Share Conversion and Private Information Retrieval by Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov
See my comments.

[Pointed out by Avi, July 23, 2012] (CT)
On simple functions, non-determinism, and depth-three circuits by Les Valiant (1977 and 1983).
See my comments.

[Pointed out by Or, July 22, 2012] (CT)
Every NL set has constant-depth Boolean circuits of sub-exponential size (folklore?)
See my comments.

[MIT, Aug 15-17, 2012] (RnC)
A small sample of RANDOM+APPROX 2012 talks [LNCS 7408]
See my comments.

[Seen on ECCC, Sept 13, 2012] (PRG)
A Derandomized Switching Lemma and an Improved Derandomization of AC0 by Luca Trevisan and TongKe Xuey.
See my comments.

[Seen on ECCC, Sept 25, 2012] (CT)
Proof vs. Truth in Computational Complexity by Boaz Barak.
See my comments.

[Seen on ECCC, Oct 11, 2012] (PRG)
Better pseudorandom generators from milder pseudorandom restrictions by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan
See my comments.

[Email discussion with Rafi, Nov 5, 2012] (CRY)
How to Garble RAM Programs by Steve Lu and Rafail Ostrovsky
See my comments.

[Seen on ECCC, Nov 15, 2012] (PT)
These two independent works on Conditional Samples in Distribution Testing:
(1) On the Power of Conditional Samples in Distribution Testing by Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah
(2) Testing probability distributions using conditional samples by Clement Canonne, Dana Ron, and Rocco Servedio
See my comments.

[Seen on ECCC, Nov 26, 2012] (PT)
Strong LTCs with inverse polylogarithmic rate and soundness by Michael Viderman
See my comments.

[Guy at Weizmann's TOC seminar, Dec 31, 2012] (PPS)
Interactive Proofs of Proximity: Delegating Computation in Sublinear Time by Guy Rothblum, Salil Vadhan, and Avi Wigderson.
See my comments.

[Pointed out by Or, Jan 1, 2013] (CT)
Natural Proofs Versus Derandomization by Ryan Williams
See my comments.

[Seen on ECCC, Feb 6, 2013] (PT)
Strong LTCs with inverse poly-log rate and constant soundness by Michael Viderman
See my comments.

[Seen on ECCC, Feb 8, 2013] (EXT)
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy by Xin Li
See my comments.

[Seen on ECCC, Feb 19, 2013] (PT)
A ${o(n)}$ monotonicity tester for Boolean functions over the hypercube by Deeparnab Chakrabarty and C. Seshadhri
See my comments.

[Tokyo, March 4-6, 2013] (CRY)
My choice of highlights from the 10th Theory of Cryptography Conference (TCC) includes
1. A Counterexample to the Chain Rule for Conditional HILL Entropy by S. Krenn, K. Pietrzak, and A. Wadia
2. Languages with Efficient Zero-Knowledge PCPs are in SZK by M. Mahmoody and D. Xiao
3. Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments by R. Pass
4. Invited Talk by Tal Malkin on Secure Computation for Big Data
5. Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy by K. Dixit, M. Jha, S. Raskhodnikova, and A. Thakurta
6. Invited Talk by Benny Applebaum on Cryptographic Hardness of Random Local Functions
See my comments regarding these talks as well as a larger sample of TCC'13 talks.

[Private communication by Tom and Ron, Spring 2013] (PPS)/(PT)
Non-Interactive Proofs of Proximity by Tom Gur and Ron Rothblum
See my comments.

[Seen in CC Vol 22-2 (missed at CCC'12), June 3rd, 2013] (RnC)
Is Valiant-Vazirani's Isolation Probability Improvable? by Holger Dell, Valentine Kabanets, Dieter van Melkebeek, and Osamu Watanabe
See my comments, better late than never.

[Seen on ECCC, June 9th, 2013] (CT)
Communication is bounded by root of rank by Shachar Lovett.
See my comments.

[Pointed out by Or, June 15, 2013] (RnC)
Local Correctability of Expander Codes by Brett Hemenway, Rafail Ostrovsky, and Mary Wootters
See my comments.

[Jonathan in WIS's theory lunch, June 19, 2013] (CRY)
Answering $n^{2+o(1)}$ Counting Queries with Differential Privacy is Hard by Jonathan Ullman
See my comments.

[Dana's talk at a Property Testing workshop, June 18, 2013] (PT)
Exponentially improved algorithms and lower bounds for testing signed majorities by Dana Ron and Rocco Servedio
See my comments.

[Seen on ECCC, June 26, 2013] (PPS)
Constant rate PCPs for circuit-SAT with sublinear query complexity by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth
See my comments.

[Ron in WIS's theory lunch, June 26, 2013] (PPS)
Delegation for Bounded Space by Yael Tauman Kalai, Ran Raz, and Ron Rothblum
See my comments.

[Reminded of Andrej's talk at WIS (in May 2010), June 29, 2013] (PT)
A better tester for bipartiteness? by Andrej Bogdanov and Fan Li
See my comments, better late than never.

[Pointed out by Or, June 29, 2013] (RnC)
Constructing Hard Functions from Learning Algorithms by Adam Klivans, Pravesh Kothari, and Igor Oliviera.
See Or's and Oded's comments.

[Pointed out by Or, June 29, 2013] (RnC)
Interactive Channel Capacity by Gillat Kol and Ran Raz.
See my comments.

[Benny at the WIS theory seminar, July 1, 2013] (CRY)
Locally Computable Universal One-Way Hash Functions with Linear Shrinkage by Benny Applebaum and Yoni Moses
See my comments.

[Gilad at the WIS theory lunch, July 3, 2013] (PT)/(RnC)
Tight Approximation of Image Matching by Simon Korman, Daniel Reichman, and Gilad Tsur
See my comments.

[A word of mouth, July 7, 2013] (PPS)/(CT)
Analytical Approach to Parallel Repetition by Irit Dinur and David Steurer
See my comments.

[Seen on ECCC, July 18, 2013] (CT)
A Uniform Min-Max Theorem with Applications in Cryptography by Salil Vadhan and Colin Jia Zheng
See my comments.

[Reminded by a talk at CTW (see Item 4), July 30, 2013] (CT)
Approximation Resistance from Pairwise Independent Subgroups by Siu On Chan
See my comments.

[CTW, Aarhus, July 30, 2013] (RnC)
Some talks at the China Theory Week
1. Chenggang Wu: Testing Surface Area
2. Huy L. Nguyen: Approximate Near Neighbor Search Beyond Locality Sensitive Hashing
3. Reut Levi: A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
4. Sangxia Huang: Improved Hardness of Approximating Chromatic Number
5. Avishay Tal: Properties and Applications of Boolean Function Composition
6. Zeyu Guo: Randomness-Efficient Curve Samplers
See my comments.

[Pointed out by Or, August 8, 2013] (CT)
Approximating Boolean functions with depth-2 circuits by Eric Blais and Li-Yang Tan.
See my comments.

[Private communication by Ron, Fall 2012] [(I waited for) ECCC posting, Aug 9, 2013] (CRY)
Efficient Multiparty Protocols via Log-Depth Threshold Formulae by Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, and Ron Rothblum
See my comments.

[Pointed out by Boaz, August 22, 2013] (CRY)
Two papers on Obfuscation, Non-Black-Box Simulation, and Resettable Cryptography by Nir Bitansky and Omer Paneth
1. From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique;
2. On the impossibility of approximate obfuscation and applications to resettable cryptography
See my comments.

[Seen on ECCC, Aug 24, 2013] (PT)
Instance-by-instance optimal identity testing by Gregory Valiant and Paul Valiant
See my comments.

[Pointed out by Boaz, Aug 27, 2013] (PT)
Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters
See my comments.

[Discusson with Gil, Aug 31, 2013] (CT)
A taste of Circuit Complexity Pivoted at NEXP not in ACC0 (and more) by Gil Cohen
See my comments.

[Seen on ECCC, Sept 3, 2013] (CT)
Algorithms versus Circuit Lower Bounds by Igor Oliveira
See my comments.

[Mihir talk at GM-Fest, MIT, Sept 7, 2013] (CRY)
Instantiating Random Oracles via UCEs by Mihir Bellare, Viet Tung Hoang, and Sriram Keelveedhi
See my comments.

[Email from Sesh, Sept 10, 2013] (PT)
The Property Testing Review Website
See details on this new site.

[Seen on ECCC, Sept 13, 2013] (CT)
Two works regarding the complexity of deciding properties of sampleable distributions by Thomas Watson
1. The Complexity of Estimating Min-Entropy, ECCC TR12-070. 2. The Complexity of Deciding Statistical Properties of Samplable Distributions, ECCC TR13-124.
See my comments.

[Igor at WIS's TOC seminar, Nov 4, 2013]
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball by Itai Benjamini, Gil Cohen, and Igor Shinkar
See my comments.

[Seen on ECCC, Nov 20, 2013] (CT)
$(2+\epsilon)$-SAT is NP-hard by Per Austrin, Venkatesan Guruswami, and Johan Hastad
See my comments.

[Weizmann Institute, Dec 10-12, 2013]
Celebration of the work of Shafi Goldwasser and Silvio Micali featuring of a day of TOC lectures and a two-day workshop on theory of cryptography.
See the event's website and my comments (which actually add nothing).

[Julia at WIS's TOC seminar, Dec 22, 2013]
Polynomial Bounds for the Grid-Minor Theorem by Chandra Chekuri and Julia Chuzhoy
See my comments.

[Or at WIS's TOC seminar, Jan 6, 2014] (CT)
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture by Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson.
See my comments.

[Private communication by Elazar and Igor, Fall 2013] (PT)
Direct Sum Testing by Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar
See my comments.

[Dagstuhl, 16-21 March 2014] (CT)
Dagstuhl workshop on Computational Complexity of Discrete Problems (a selection of twenty talks)
See my comments.

[Seen on ECCC, 11 April 2014] (CT)
Exponential Separation of Information and Communication by Anat Ganor, Gillat Kol, and Ran Raz
See my comments.

[Found at random on arXiv, 30 April 2014] (CT)
On Uniform Reductions between Direct Product and XOR Lemmas by Ragesh Jaiswal
See my comments.

[Theory lunch at Weizmann, 21 May 2014]
Hybrid Stretch and Sourcewise Spanners by Merav Parter
See my comments.

[Pointed out by Roei Tell, 12 June 2014] (RnC)
Every locally characterized affine-invariant property is testable by Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.
See my comments.

[Noticed on ECCC (three days too late), 27 July 2014] (RnC)
2-Server PIR with sub-polynomial communication by Zeev Dvir and Sivakanth Gopi
See my comments.

[Seen on ECCC, 10 August 2014] (RnC)
Locally Correctable and Testable Codes Approaching the Singleton Bound by Or Meir
See my comments.

[Seen on ECCC, 10 August 2014] (CT/CRY)
On Basing Size-Verifiable One-Way Functions on NP-Hardness by Andrej Bogdanov and Christina Brzuska
See my comments.

[Seen on ECCC, 10 August 2014] (CT)
Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem by Craig Gentry
See my comments.

[Seen on ECCC, 20 August 2014] (CT)
Separation between Estimation and Approximation by Uriel Feige and Shlomo Jozeph.
See my comments.

[Seen on ECCC, 27 August 2014] (CT)
Exponential Separation of Information and Communication for Boolean Functions by Anat Ganor, Gillat Kol, and Ran Raz
See my comments.

[Seen in STOC'14 proceedings, 28 August 2014] (PT)
$L_p$-testing by Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev.
See my comments.

[Barcelona, Sept 4-6 2014] (RnC)
One Approx'14 invited talk and eight Random'14 un-invited talks
See my comments.

[Philadelphia, October 19-21, 2014]
A few works from FOCS'14
(1) Preventing False Discovery in Interactive Data Analysis is Hard by Moritz Hardt and Jonathan Ullman
(2) New algorithms and lower bounds for monotonicity testing by Xi Chen, Rocco Servedio, and Li-Yang Tan
(3) Path-Finding Methods for Linear Programming: Solving Linear Programs in tildeO(sqrt(rank)) Iterations and Faster Algorithms for Maximum Flow by Yin Tat Lee and Aaron Sidford
Additional works have appeared as prior choices.
See my comments.

[Benny at WIS's theory semianr, Nov 17 2014] (CRY)
Arithmetic Cryptography by Benny Applebaum, Jonathan Avron, and Christina Brzuska.
See my comments.

[Seen on ECCC, Dec 8 2014] (RnC)
Communication with Imperfectly Shared Randomness by Clement Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan.
See my comments.

[Seen on ECCC, Dec 8 2014] (PT)
A Chasm Between Identity and Equivalence Testing with Conditional Queries by Jayadev Acharya, Clement Canonne, and Gautam Kamath.
See my comments.

[Omer at Weizmann's theory seminar, Dec 15 2014] (RnC)
Guilt-Free Interactive Data Analysis: The Reusable Holdout by Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth.
See my comments.

[Gil at a private meeting, Dec 25 2014] (EXT)
Zero-Fixing Extractors for Sub-Logarithmic Entropy by Gil Cohen and Igor Shinkar
See my comments.

[Belatedly seen on ECCC, Dec 31 2014] (CT)
Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses by Holger Dell and Dieter van Melkebeek.
See my comments.

[``Belatedly'' posted on ECCC, Jan 22 2015] (PT)
On Monotonicity Testing and Boolean Isoperimetric type Theorems by Subhash Khot, Dor Minzer, and Muli Safra.
See my comments.

[Seen on ECCC, Feb 5 2015] (PT)
Explicit Strong LTCs with inverse poly-log rate and constant soundness by Michael Viderman
See my comments.

[Seen on ECCC, March 9 2015] (EXT)
Three-Source Extractors for Polylogarithmic Min-Entropy by Xin Li
See my comments.

[private presentation, March 19 2015] (CT)
Tight bounds on The Fourier Spectrum of AC0 by Avishay Tal
See my comments.

[Gil at WIS's theory seminar, March 23 2015] (EXT)
Local Correlation Breakers and Applications to Mergers and Multi-Source Extractors by Gil Cohen
See my comments.

[Robi at WIS's theory lunch, March 25 2015] (RnC)
The Sketching Complexity of Graph Cuts by Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
See my comments.

[Nir at WIS's theory seminar, March 30 2015] (CT)
On the Cryptographic Hardness of Finding a Nash Equilibrium by Nir Bitansky, Omer Paneth, and Alon Rosen
See my comments.

[Seen on ECCC, April 3 2015] (CRY)
Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz
See my comments.

[Seen on ECCC, May 7 2015] (RnC)
A simple proof of the Isolation Lemma by Noam Ta-Shma
See my comments.

[private presentation by Or, April-May 2015] (RnC)
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity by Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf
See my comments.

[Seen on ECCC, May 23 2015] (PPS)
Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition by Irit Dinur, Prahladh Harsha, and Guy Kindler
See my comments.

[Seen on ECCC, June 1st 2015] (PT)
Trading query complexity for sample-based testing and multi-testing scalability by Eldar Fischer, Oded Lachish, and Yadu Vadusev
See my comments.

[Seen on ECCC, June 15th 2015] (EXT)
Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs by Gil Cohen
See my comments.

[Seen on ECCC, July 24th 2015] (EXT)
Explicit Two-Source Extractors and Resilient Functions by Eshan Chattopadhyay and David Zuckerman
See my comments.

[Seen on ECCC, August 6th 2015] (EXT)
Improved Constructions of Two-Source Extractors by Xin Li
See my comments.

[Seen on ECCC, Sept 2nd 2015] (EXT)
Explicit resilient functions matching Ajtai-Linial by Raghu Meka
See my comments.

[Presentation by Amir Shpilka, Nov 17th 2015] (RnC)
Bipartite Perfect Matching is in quasi-NC by Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
See my comments.

[Seen on ECCC, Nov 17th 2015] (EXT)
Non-Malleable Extractors - New Tools and Improved Constructions by Gil Cohen
See my comments.

[Tomer at the ML and Statistic seminar of Weizmann, Dec 16th 2015]
The Computational Power of Optimization in Online Learning by Elad Hazan and Tomer Koren
See my comments.

[Amir at the TOC seminar of Weizmann, Dec 28th 2015] (CT)
Hardness in P (an overview) by Amir Abboud
See my comments.

[Johns Hopkins University, January 7-9, 2016] (PT)
Notes from the Sublinear Algorithms Workshop
See my comments.

[Seen on ECCC, February 5, 2016] (EXT)
Randomness Extraction in AC0 and with Small Locality by Kuan Cheng and Xin Li
See my comments.

[Seen on ECCC, February 5, 2016] (CT)
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning by Ran Raz
See my comments.

[Weizmann's theory lunch, February 10, 2016] (CT)
The Power of Depth for Feedforward Neural Networks by Ronen Eldan and Ohad Shamir
See my comments.

[Seen on ECCC, April 15, 2016] (CT)
Can PPAD Hardness be Based on Standard Cryptographic Assumptions? by Alon Rosen, Gil Segev, and Ido Shahaf
See my comments.

[Finally posted on ECCC, April 17, 2016] (PPS)
Constant-Round Interactive Proofs for Delegating Computation by Omer Reingold, Guy Rothblum, and Ron Rothblum
See my comments.

[Merav at WIS's theory seminar, May 2, 2016] (RnC)
MST in Log-Star Rounds of Congested Clique by Mohsen Ghaffari and Merav Parter
See my comments.

[Seen on ECCC, May 9, 2016] (PT)
A New Approach for Testing Properties of Discrete Distributions by Ilias Diakonikolas and Daniel Kane
See my comments.

[Stephen at Weizmann's TOC seminar, May 23, 2016] (RnC)
Beating CountSketch for Heavy Hitters in Insertion Streams by Vladimir Braverman, Stephen Chestnut Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David Woodruff
See my comments.

[Seen in the 48th STOC proceedings, June 24, 2016] (RnC)
Instance Optimal Learning of Discrete Distributions by Gregory Valiant and Paul Valiant.
See my comments.

[Seen in the 48th STOC proceedings, June 24, 2016] (PT)
A Polynomial Lower Bound for Testing Monotonicity by Aleksandrs Belovs and Eric Blais
See my comments.

[Seen in the 48th STOC proceedings, June 25, 2016] (PRG)
Algebraic Attacks against Random Local Functions and Their Countermeasures by Benny Applebaum and Shachar Lovett
See my comments.

[Seen on ECCC, July 18, 2016] (EXT)
Low-error two-source extractors for polynomial min-entropy by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma.
See my comments.

[Suggested by Or Meir, July 18, 2016] (CT)
No occurrence obstructions in geometric complexity theory by Peter Burgisser, Christian Ikenmeyer, and Greta Panova
See my comments.

[Suggested by Or Meir, August 2, 2016] (CT)
Improving the lower bound on size complexity of explicit functions and some limitations on subsequent improvements by Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Knop, and Alexander Kulikov.
See my comments.

[Seen on ECCC, August 25, 2016] (PT)
A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness by Deeparnab Chakrabarty and C. Seshadhri
See my comments.

[Seen on ECCC and digested, August 29, 2016] (RnC)
Local Expanders by Emanuele Viola and Avi Wigderson
See my comments.

[Approx'16, Paris, Sept 7, 2016] (CT)
Proving weak approximability without algorithms by Ridwan Syed and Madhur Tulsiani
See my comments.

[Belatedly seen on ECCC, Sept 2016] (RnC)
Perfect Bipartite Matching in Pseudo-Deterministic RNC by Shafi Goldwasser and Ofer Grossman
See my comments.

[MSR and MIT, Oct 2016] (RnC)
Brief report of the Workshop on Local Algorithms featuring two surveys and five works.
See my report.

[Seen on ECCC, Oct. 28, 2016] (CT)
NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications by Joshua Grochow
See my comments.

[Discussion with Zeev Dvir, Oct 2016] (CT)
On the non-rigidity of generating matrices of good codes by Zeev Dvir (written by Oded).
See the actual text.

[Private presentation by Tom; posted on ECCC, Nov 2, 2016] (PT)
Alice and Bob Show Distribution Testing Lower Bounds by Eric Blais, Clement Canonne, and Tom Gur
See my comments.

[Private presentation by Avishay; posted on ECCC, Nov 16, 2016] (CT)
Computing Requires Larger Formulas than Approximating by Avishay Tal
See my comments.

[Julia at WIS's TOC seminar, Nov 27, 2016]
New Hardness Results for Routing on Disjoint Paths by Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
See my comments.

[Seen on ECCC, Dec 13, 2016] (RnC)
Pseudodeterministic Constructions in Subexponential Time by Igor Carboni Oliveira amd Rahul Santhanam.
See my comments.

[Seen on ECCC, Dec 19, 2016] (PT)
A Characterization of Constant-Sample Testable Properties by Eric Blais and Yuichi Yoshida.
See my comments.

[Amir at a special seminar at WIS, Jan 12, 2017] (CT)
Hardness in P (survey talk) by Amir Abboud
See my comments.

[Seen on ECCC, Feb 8, 2017] (CT)
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing by Ilan Komargodski, Moni Naor, and Eylon Yogev
See my comments.

[Posted on ECCC, Feb 28, 2017] (CT)
Average-Case Fine-Grained Hardness by Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
See my comments.

[Posted on ECCC, Apr 9, 2017] (CRY)
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) by Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh Kothari
See my comments.

[Received as a gift on Apr 19, 2017] (CRY)
Tutorials on the Foundations of Cryptography edited by Yehuda Lindell
See my comments.

[Seen on ECCC, Apr 23, 2017] (PT)
Settling the query complexity of non-adaptive junta testing by Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie
See my comments.

[Luca at the TOC seminar of WIS, Apr 24, 2017]
Some Simple Distributed Network Processes by Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra,m and Luca Trevisan.
See my comments.

[Posted on ECCC, May 11, 2017] (PT) (CT)
High dimensional expanders imply agreement expanders by Irit Dinur and Tali Kaufman
See my comments.

[Pasin at WIS's TheoryLunch, May 24, 2017] (CT)
ETH-hardness of Approximating Densest k-Subgraph by Pasin Manurangsi
See my comments.

[Seen on ECCC, June 1, 2017] (CRY)
Multi Collision Resistant Hash Functions and their Applications by Itay Berman, Akshay Degwekar, Ron Rothblum, and Prashant Nalini Vasudevan
See my comments.

[Montreal, June 19-23, 2017]
On the 49th STOC (and Theory Fest 2017). The Highlights of my report include
* Explicit, Almost Optimal, Epsilon-Balanced Codes by Amnon Ta-Shma.
* Avi Wigderson: On the Nature and Future of ToC
* Competitive Distribution Estimation: Why is Good-Turing Good by Alon Orlitsky
* Orna Kupferman: Examining classical graph-theory problems from the viewpoint of formal-verification methods
* An Improved Distributed Algorithm for Maximal Independent Set by Mohsen Ghaffari.
See my report.

[Rohit at WIS's TheoryLunch, July 10, 2017] (RnC)
Derandomizing Isolation Lemma: a geometric approach by Stephen Fenner, Rohit Gurjar and Thomas Thierauf.
See my comments.

[Seen on ECCC, July 18, 2017] (CT)
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds by Kasper Green Larsen, Omri Weinstein, and Huacheng Yu.
See my comments.

[Seen on ECCC, August 16, 2017] (CT)
The Direct Sum of Universal Relations by Or Meir
See my comments.

[Seen on ECCC, Sept 8, 2017] (PT)
Two works related to testing uniformity of distributions by Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price, and Alistair Stewart
See my comments.

[a belated report, Oct 3, 2017] (CT)
Advances in quantified derandomization of constant-depth circuits two works by Roei Tell
See my comments.

[Seen on ECCC, Oct 8, 2017] (CT) (RnC)
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds by Or Meir and Avi Wigderson
See my comments.

[Seen on PTreview, Oct 10, 2017] (PT)
Efficient Removal without Efficient Regularity by Lior Gishboliner and Asaf Shapira
See my comments.

[Seen on Roei's expositions page, Oct 11, 2017] (CT)
Non-trivial derandomization implies weak lower bounds: An exposition of an (almost) elementary proof by Roei Tell
See my comments.

[Seen on ECCC, Oct 13, 2017] (PT)
Proofs of Proximity for Distribution Testing by Alessandro Chiesa and Tom Gur
See my comments.

[Seen on ECCC, Nov 1, 2017] (PRG)
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs by Mark Braverman, Gil Cohen, and Sumegha Garg
See my comments.

[Seen on ECCC, Nov 1, 2017] (CRY)
From Laconic Zero-Knowledge to Public-Key Cryptography by Itay Berman, Akshay Degwekar, Ron Rothblum, and Prashant Nalini Vasudevan
See my comments.

[ITCS'18 posted program, Nov 28, 2017]
A selection from the ITCS'18 program.
* Pseudo-Deterministic Proofs by Shafi Goldwasser, Ofer Grossman and Dhiraj Holden.
* Zero-Knowledge Proofs of Proximity by Itay Berman, Ron Rothblum and Vinod Vaikuntanathan.
* Relaxed Locally Correctable Codes by Tom Gur, Govind Ramnarayan and Ron Rothblum.
* Learning by Refuting by Pravesh K Kothari and Roi Livni.
* Edge Estimation with Independent Set Oracles by Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian and Makrand Sinha.
* ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network by Irit Dinur and Pasin Manurangsi.
* Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs by Shay Solomon.
See my comments.

[Benny at the WIS complexity club, Nov 29, 2017] (CT)
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions by Benny Applebaum
See my comments.

[Seen on ECCC, Dec 14, 2017] (CT)
Agreement tests on graphs and hypergraphs by Irit Dinur, Yuval Filmus, and Prahladh Harsha
See my comments.

[Private presentation by Roei Tell, Dec 28, 2017] (CT)
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP by Cody Murray and Ryan Williams
See my comments.

[Private presentation by Roei Tell, Dec 28, 2017] (CT)
Proving that prBPP=prP is as hard as ``almost'' proving that P neq NP by Roei Tell
See my comments.

[Pointed out by Irit Dinur, Jan 10, 2018] (CT)
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor Minzer, and Muli Safra
See my comments.

[Seen on ECCC, Jan 11, 2018] (PT)
A Generalized Turan Problem and its Applications by Lior Gishboliner and Asaf Shapira
See my comments.

[Eylon at the WIS theory seminar, Jan 11, 2018] (CRY)
Distributed computing made secure: A new cycle cover theorem by Merav Parter and Eylon Yogev
See my comments.

[Ofer at the WIS theory seminar, Jan 22, 2018] (RnC)
Reproducibility in Randomized Log-space by Ofer Grossman and Yang Liu.
See my comments.

[Seen on ECCC, Feb 2, 2018] (PPS)
Efficient Batch Verification for UP by Omer Reingold, Guy Rothblum, and Ron Rothblum
See my comments.

[Uri at WIS's Theory Lunch, March 14, 2018] (PT)
Approximate Modularity, Revisited by Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen.
See my comments.

[Seen on ECCC, May 21, 2018] (PT)
Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs by Akash Kumar, C. Seshadhri, and Andrew Stolman
See my comments.

[Seen on ECCC, June 9, 2018] (PRG)
Pseudorandom Generators for Width-3 Branching Programs by Raghu Meka, Omer Reingold, and Avishay Tal
See my comments.

[Seen on ECCC, June 11, 2018] (PT)
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs by Amit Levi and Erik Waingarten.
See my comments.

[Seen on ECCC, June 25, 2018] (PRG)
A Tight Lower Bound for Entropy Flattening by YiHsiu Chen, Mika Goos, Salil Vadhan, and Jiapeng Zhang
See my comments.

[Interaction with the authors, May-July 2018] (PPS/CRY)
An Efficiency-Preserving Transformation from Honest-Verifier Statistical Zero-Knowledge to Statistical Zero-Knowledge by Pavel Hubacek and Alon Rosen and Margarita Vald
See my comments.

[Recommended by Eric Blais, August 21, 2018] (PT)
Near log-convexity of measured heat in (discrete) time and consequences by Mert Saglam
See my comments.

[Discussions with Roei, 27Sept-3Oct, 2018] (PRG)
Does the Choice of Expander Matter for Expander-Based One-way Function? on a paper by Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell
See my comments.

[Oberwolfach, Nov 11-16, 2018] (CT)
Comments on some talks presented at a complexity workshop
See my comments.

[Seen on ECCC, Nov 25, 2018] (CT)
Bootstrapping Results for Threshold Circuits ``Just Beyond'' Known Lower Bounds by Lijie Chen and Roei Tell
See my comments.

[Julia at Weizmann's TOC seminar, Jan 7, 2019]
Almost polynomial hardness of node-disjoint paths in grids by Julia Chuzhoy, David H.K. Kim, and Rachit Nimavat.
See my comments.

[ITCS, UCSD, Jan 10-11, 2019]
On a few works presented at ITCS'19
See my comments.

[Seen on ECCC, Jan 27, 2019] (PRG)
Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders by Benny Applebaum and Eliran Kachlon
See my comments.

[Eylon at WIS's theory seminar, Feb 4, 2019] (PPS)
The power of distributed verifiers in interactive proofs Moni Naor, Merav Parter and Eylon Yogev
See my comments.

[posted on ECCC, Feb 26, 2019] (PPS)
Smooth and Strong PCPs by Orr Paradise
See my comments.

[talk in WIS's TOC seminar, Mar 25, 2019] (CRY)
Homomorphic Secret Sharing (survey) by Yuval Ishai
See my comments.

[seen on ECCC, Apr 1, 2019] (PT)
Random walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs by Akash Kumar, C. Seshadhri, and Andrew Stolman
See my comments.

[Private presentation by Tal Herman, Apr 11, 2019] (RnC)
Statistical Difference Beyond the Polarizing Regime by Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan
See my comments.

[Posted on ECCC, Apr 14, 2019] (RnC)
A Lower Bound for Relaxed Locally Decodable Codes by Tom Gur and Oded Lachish
See my comments.

[Got reminded of this posting, May 29, 2019] (CT)
Karp-Lipton theorems: Translating non-uniform `collapses' into uniform `collapses' (an exposition) by Roei Tell
See my comments.

[Dana at WIS's TOC seminar, June 17, 2019] (CT)
Nearly Optimal Derandomization under Assumptions by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
See my comments.

[Dylan at STOC'19, June 26, 2019] (CT)
Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes by Dylan McKay, Cody Murray, and Ryan Williams
See my comments.

[Phoenix, June 23-26, 2019]
On twelve STOC'19 presentations
(1) Bootstrapping Results for Threshold Circuits Just Beyond Known Lower Bounds by Chen and Tell
(2) The Log-Approximate-Rank Conjecture is False by Chattopadhyay, Mande, and Sherif
(3) Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme by Nanongkai, Saranurak, and Yingchareonthawornchai
(4) Distributed Edge Connectivity in Sublinear Time by Daga, Henzinger, Nanongkai, and Saranurak
(5) Towards the Locality of Vizing's Theorem by Su and Vu
(6) Testing Graphs against an Unknown Distribution by Gishboliner and Shapira
(7) Testing Unateness Nearly Optimally by Chen and Waingarten
(8) Random walks and forbidden minors II: a poly(d/epsilon)-query tester for minor-closed properties of bounded degree graphs by Kumar, Seshadhri, and Stolman
(9) Static Data Structure Lower Bounds Imply Rigidity by Dvir, Golovnev, and Weinstein
(10) Solving Linear Programs in the Current Matrix Multiplication Time by Cohen, Lee, and Song
(11) Sylvester-Gallai type theorems for quadratic polynomials by Shpilka
(12) Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes by McKay, Murray, and Williams
See my comments.

[Partas, July 11, 2019]
On three ICALP'19 presentations
(1) Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set by Nabil Mustafa
(2) Fine-Grained Complexity of Dynamic Programming Problems (survey) by Karl Bringmann
(3) A Quest Towards Strong Unconditional Lower Bounds (survey) by Kasper Green Larsen
See my comments.

[Zurich, July 20-22, 2019]
On the 3rd Workshop on Local Algorithms (WOLA'19)
See my comments.

[PapaFest, Columbia, Sept 6, 2019]
An Improved Approximation Algorithm for TSP in the Half Integral Case by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan
See my comments.

[Private discussions with Zeev, Sept 13, 2019] (CT)
Fourier and Circulant Matrices Are Not Rigid by Zeev Dvir and Allen Liu
See my comments.

[MIT, September 20-22, 2019]
On few presentation at the RANDOM'19 conference
See my comments.

[Theory Seminar of Columbia, Sept 25, 2019] (CT)
Lifting Lower Bounds, Communication, and Proofs a survey talk by Toniann Pitassi
See my comments.

[Theory Seminar of Columbia, Sept 27, 2019] (PT)
Junta correlation is testable by Anindya De, Elchanan Mossel, and Joe Neeman.
See my comments.

[Seen on ECCC, Oct 4, 2019] (PT)
Finding monotone patterns in sublinear time by Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, and Erik Waingarten
See my comments.

[Seen on ECCC, Nov 5, 2019] (CT)
Optimal Inapproximability with Universal Factor Graphs by Per Austrin, Jonah Brown-Cohen, and Johan Hastad
See my comments.

[Seen on ECCC, Nov 7, 2019] (PT)
Almost Optimal Testers for Concise Representations by Nader Bshouty
See my comments.

[FOCS19, Nov 9th 2019]
Why I Am Excited About This Research Direction: A Tribute to Shafi Goldwasser by Madhu Sudan, Huijia (Rachel) Lin, Maria-Florina (Nina) Balcan, and Ronitt Rubinfeld
See my comments.

[Baltimore, Nov 10-12th 2019]
A sample of FOCS19 presentations (a partial list includes)
* Derandomization from Algebraic Hardness: Treading the Borders by Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon
* Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error by Benny Applebaum and Eliran Kachlon
* Lower bounds for maximal matchings and maximal independent sets by Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikal Rabie, and Jukka Suomela
* Efficient Construction of Rigid Matrices Using an NP Oracle by Josh Alman and Lijie Chen
* Truly Optimal Euclidean Spanners by Hung Le and Shay Solomon
* Hardness Magnification for all Sparse NP Languages by Lijie Chen, Ce Jin, and Ryan Williams
* The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs by Enric Boix-Adsera, Matthew Brennan, and Guy Bresler
* Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits by Lijie Chen
* Agreement testing theorems on layered set systems by Yotam Dikstein and Irit Dinur
* A characterization of graph properties testable for general planar graphs with one-sided error (It's all about forbidden subgraphs) by Artur Czumaj and Christian Sohler
See my comments.

[CU's Theory Seminar, Feb 18, 2020]
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators by Alexandr Andoni, Clifford Stein, and Peilin Zhong
See my comments.

[Got reminded, Feb 29th 2020] (CT)
High-precision estimation of random walks in small space by AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan.
See my comments.

[Suggested by an anonymous friend, Mar 2nd 2020] (PT)
Testing Linear Inequalities of Subgraph Statistics by Lior Gishboliner, Asaf Shapira, and Henrique Stagni.
See my comments.

[Seen on ECCC, Mar 22nd 2020]
Error Correcting Codes for Uncompressed Messages by Ofer Grossman and Justin Holmgren.
See my comments.

[Discussion with Roei, April 2020] (CT)
On implications of better sub-exponential lower bounds for AC0 by Roei Tell
See my comments.

[Seen on ECCC, 26 April 2020] (PPS)
Interactive Proofs for Verifying Machine Learning by Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff
See my comments.

[Seen on ECCC, 24 June 2020] (CT)
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? by Ronen Shaltiel
See my comments.

[Seen on ECCC, 5 July 2020] (RnC)
Impossibility of Derandomizing the Isolation Lemma for all Families by Manindra Agrawal, Rohit Gurjar, and Thomas Thierauf
See my comments.

[Seen on ECCC, 6 July 2020] (CT)
KRW Composition Theorems via Lifting by Susanna de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, and Robert Robere
See my comments.

[Seen on ECCC, 13 Sept 2020] (CT)
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs by William Hoza, Edward Pyne, and Salil Vadhan
See my comments.

[Seen on ECCC, 20 Sept 2020] (RnC)
Relaxed Locally Correctable Codes with Improved Parameters by Vahid Reza Asadi and Igor Shinkar
See my comments.

[Seen on ECCC, 24 Sept 2020] (PPS)
Batch Verification for Statistical Zero Knowledge Proofs by Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, and Adam Sealfon
See my comments.

[Seen on ECCC, 29 Sept 2020] (PRG)
Simple and Fast Derandomization from Very Hard functions: Eliminating Randomness at Almost No Cost by Lijie Chen and Roei Tell
See my comments.

[Seen on ECCC, 10 Oct 2020] (RnC)
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy by Marcel Dall'Agnol, Tom Gur, and Oded Lachish.
See my comments.

[Seen on ECCC, 29 Oct 2020] (PPS)
Batch Verification and Proofs of Proximity with Polylog Overhead by Guy Rothblum and Ron Rothblum
See my comments.

[Seen on ECCC, 3 Dec 2020] (CT)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0 by Yuval Filmus, Or Meir, and Avishay Tal.
See my comments.

[Seen on ECCC, 30 Jan 2021] (PT)
Random walks and forbidden minors III: poly(d/eps)-time partition oracles for minor-free graph classes by Akash Kumar, C. Seshadhri, and Andrew Stolman.
See my comments.

[Seen on ECCC, 20 Feb 2020] (PRG)
Three works on pseudorandomness posted today
* Monotone Branching Programs: Pseudorandomness and Circuit Complexity by Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan
* Pseudodistributions That Beat All Pseudorandom Generators by Edward Pyne and Salil Vadhan
* Error Reduction For Weighted PRGs Against Read Once Branching Programs by Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma
See my comments.

[Seen on ECCC, 6 Mar 2021] (PPS)
Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge) by Justin Holmgren, Alex Lombardi, and Ron Rothblum
See my comments.

[Seen on ECCC, 20 Mar 2021]
Promise Problems Meet Pseudodeterminism by Peter Dixon, A. Pavan, and N.V. Vinodchandran
See my comments.

[Seen on ECCC, 27 Mar 2021] (PRG)
Better Pseudodistributions and Derandomization for Space-Bounded Computation by William Hoza
See my comments.

[Seen on PT review, 31 Mar 2021] (PT)
Testing Hamiltonicity (and other problems) in Minor-Free Graphs by Reut Levi and Nadav Shoshan
See my comments.

[Seen in the CCC program, 1 June 2021] (PT)
GSF-locality is not sufficient for proximity-oblivious testing by Isolde Adler, Noleen Kohler, and Pan Peng
See my comments.

[Seri at WIS's TheoryLunch, 9 June 2021]
Improved Hardness of Approximation for Distributed Diameter by Ofer Grossman, Seri Khoury, and Ami Paz
See my comments.

[Private discussion with Roei, 10 June 2021] (CT)
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise by Lijie Chen and Roei Tell
See my comments.

[Seen on ECCC, 15 June 2021] (CT)
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits by Nutan Limaye, Srikanth Srinivasan, and Sebastien Tavenas
See my comments.

[Seen on ECCC, 2 July 2021] (CT)
A Note on One-way Functions and Sparse Languages by Yanyi Liu and Rafael Pass
See my comments.

[Reminded by Hila Dahari, 5 July 2021] (PPS)
On Prover-Efficient Public-Coin Emulation of Interactive Proofs by Gal Arnon and Guy Rothblum
See my comments.

[Private presentation by Merav Parter, 19 and 21 July 2021]
Algebraic methods in the congested clique by Keren Censor-Hillel, Petteri Kaski, Janne H.~Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela
See my comments.

[Private communication by Roei Tell, 7 August 2021] (CT)
On the feasibility of a seemingly modest challenge in quantified derandomization by Roei Tell
See my comments.

[Seen on ECCC, 20 August 2021] (CT)
How to Find Water in the Ocean: A Survey on Quantified Derandomization by Roei Tell
See my comments.

[Seen on ECCC, 24 August 2021] (PT)
The complexity of testing all properties of planar graphs, and the role of isomorphism by Sabyasachi Basu, Akash Kumar, and C. Seshadhri
See my comments.

[Announcement of SI-TOC, 23 September 2021] (PT)
Locally Testable Codes with Constant Rate, Distance, and Locality by Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes
See my comments.

[Amir at a faculty meeting at Weizmann, 1 December 2021]
Gomory-Hu Tree in Subcubic Time by Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi
See my comments.

[Missed on ECCC but noticed today, 2 December 2021] (PT/PPS)
Sample-Based Proofs of Proximity by Guy Goldberg and Guy Rothblum
See my comments.

[Pointed out by Dana Ron, 10 December 2021] (PT)
VC dimension and distribution-free sample-based testing by Eric Blais, Renato Ferreira Pinto Jr., and Nathaniel Harms
See my comments.

[Merav at WIS's TOC seminar, 13 December 2021]
New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier by Shimon Kogan and Merav Parter
See my comments.

[Seen on ECCC, 13 Januray 2022]
Approximating Large Powers of Stochastic Matrices in Small Space by Gil Cohen, Dean Doron, and Ori Sberlo
See my comments.

[pointed out to me by Amir Abboud, 31 March 2022]
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva
See my comments.

[Seen on ECCC, 4 April 2022] (PRG)
Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds by Manik Dhar and Zeev Dvir
See my comments.

[Seen on ECCC, 19 April 2022] (PT) (PPS)
Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties by Tal Herman and Guy Rothblum
See my comments.

[Theory Semianr at WIS, 23 May 2022] (PPS)
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead by Noga Ron-Zewi and Ron Rothblum
See my comments.

[Found on ECCC, 19 June 2022] (PRG)
Hitting Sets Give Two-Sided Derandomization of Small Space by Kuan Cheng and William Hoza
See my comments.

[David at WIS's Theory seminar, 11 July 2022] (RnC)
Fast and Simple Algorithms for All-Terminal Network Reliability by David Karger
See my comments.

[Seri at WIS's Theory lunch, 13 July 2022] (RnC)
Hardness of Approximation in P via Short Cycle Removal: Distance Oracles, Cycle Detection, and Beyond by Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir
See my comments.

[Seen on ECCC, 14 July 2022] (RnC)
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation by Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar
See my comments.

[Seen on ECCC, 16 July 2022] (RnC)
Almost Chor--Goldreich Sources and Adversarial Random Walks by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
See my comments.

[Seen on ECCC, 19 July 2022] (RnC)
On One-Sided Testing Affine Subspaces by Nader Bshouty
See my comments.

[Alex at the TOC seminar of WIS, 15 August 2022] (PT)
Stability and testability of permutations' equations by Alexander Lubotzky
See my comments.

[Seen on ECCC, 28 August 2022] (RnC)
Recent Progress on Derandomizing Space-Bounded Computation by William Hoza
See my comments.

[Got reminded of it, 30 August 2022]
Reducing All-Pairs Shortest-Path to Matrix Multiplication by Raimund Seidel (1992)
See my comments.

[Found on the web, 26 September 2022]
Lecture notes on Boolean Matrix Multiplication by Virginia Vassilevska Williams
See my comments.

[Talk at the TheoryLunch at WIS, 19 October 2022] (RnC)
On (Near-)Optimal Algorithms for Sparse Convolution by Nick Fischer
See my comments.

[Seen on ECCC, 17 November 2022]
Testing of Index-Invariant Properties in the Huge Object Model by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
See my comments.

[Seen on ECCC, 21 November 2022]
Random Walks on Rotating Expanders by Gil Cohen and Gal Maor
See my comments.

[Max at the theory lunch of WIS, 4 January 2023]
Realizable Learning is All You Need by Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
See my comments.

[TOC seminar at WIS, 30 January 2023] (RnC)
Algorithms Should Have Bullshit Detectors (or Polynomial Time Byzantine Agreement with Optimal Resilience) by Shang-En Huang, Seth Pettie and Leqi Zhu.
See my comments.

[Nathan at the theorylunch of WIS, 31 January 2023] (RnC)
Worst-Case to Expander-Case Reductions by Amir Abboud and Nathan Wallheimer
See my comments.

[Thomas at a faculty lunch of WIS, 8 February 2023]
Proving inequality between objects by proving that they cannot be approximated by Thomas Vidick
See my comments.

[Greg at the TOC semimar of WIS, 13 March 2023]
Recent Progress on Fault Tolerant Spanners by Greg Bodwin
See my comments.

[Seen on ECCC, 16 March 2023] (EXT)
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More by Xin Li
See my comments.

[Seen on ECCC, 26 April 2023] (PT)
A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
See my comments.

[Seen on ECCC, 9 May 2023] (PT)
Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error by Guy Goldberg
See my comments.

[Seen on ECCC, 25 May 2023] (RnC)
Polynomial-Time Pseudodeterministic Construction of Primes by Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, and Rahul Santhanam
See my comments.

[Seen on ECCC, 27 May 2023] (PPS)
Batch Proofs are Statistically Hiding by Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, and Prashant Nalini Vasudevan
See my comments.

[Private presentation by Omer, 1 June 2023] (PRG)
Outcome Indistinguishability by Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, and Gal Yona
See my comments.

[Private presentation by Omer, 1 June 2023] (RnC)
Generative Models of Huge Objects by Lunjia Hu, Inbal Livni-Navon, and Omer Reingold
See my comments.

[Seen on ECCC, 18 July 2023] (CT)
Depth-3 Circuits for Inner Product by Mika Goos, Ziyi Guan, Tiberiu Mosnoi
See my comments.

[Seen on ECCC, 19 July 2023] (PRG)
On the Power of Regular and Permutation Branching Programs by Chin Ho Lee, Edward Pyne, and Salil Vadhan
See my comments.

[Seen on ECCC, 25 July 2023] (PT)
Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries by Gil Cohen and Tal Yankovitz
See my comments.

[Announced talk at MIT, 26 July 2023] (PT)
On Approximating Total Variation Distance by A. Bhattacharyya, S. Gayen, K.S. Meel, D. Myrisiotis, A. Pavan, and N.V. Vinodchandran.
See my comments.

[Henry in the algorithms seminar of WIS, 1 August 2023] (PT)
Spanning Adjacency Oracles in Sublinear Time by Greg Bodwin and Henry Fleischmann
See my comments.

[Seen on ECCC, 8 August 2023] (CT)
Linear-Size Boolean Circuits for Multiselection by Justin Holmgren and Ron Rothblum
See my comments.

[Pointed out by Amir Abboud, 9 August 2023] (CT)
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More by Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
See my comments.

[Pointed out by Amir Abboud, 15 August 2023] (CT)
Four works on fine-grained reductions of approximate counting and uniform generation to decision
(*) Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision.
(*) Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Hyperedge Estimation using Polylogarithmic Subset Queries.
(*) Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle.
(*) Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Faster Counting and Sampling Algorithms Using Colorful Decision Oracle.
See my comments.

[Igor at the TOC seminar of WIS, 18 Sept 2023] (RnC)
Worst-Case to Average-Case Reductions via Additive Combinatorics by Vahid Asadi, Sasha Golovnev, Tom Gur, Igor Shinkar and Sathyawageeswar Subramanian
See my comments.

[Seen on ECCC, 29 Sept 2023] (PRG)
Counting Unpredictable Bits: A Simple PRG from One-way Functions by Noam Mazor and Rafael Pass.
See my comments.

[Seen on ECCC, 1 Nov 2023] (RnC)
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes by Pravesh Kothari and Peter Manohar
See my comments.

[Seen on ECCC, 1 Nov 2023] (PT/PPS)
Doubly-Efficient Interactive Proofs for Distribution Properties by Tal Herman and Guy Rothblum
See my comments.

[Seen in 64th FOCS, 8 Nov 2023] (RnC)
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence by Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon
See my comments.

[Seen in ECCC, 15 Nov 2023] (CT)
Tree Evaluation is in Space O(log n * log log n) by James Cook and Ian Mertz
See my comments.

[Seen in ECCC, 19 Nov 2023] (CT)
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False by Noam Mazorand Rafael Pass
See my comments.

[Seen in ECCC, 16 Dec 2023] (CT)
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms by Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka
See my comments.

[Pointed out by Guy Rothblum, 20 Dec 2023] (PPS)
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs by Gal Arnon, Alessandro Chiesa, and Eylon Yogev.
See my comments.

[Got reminded, 25 Dec 2023] (PPS)
Constant-Round Arguments from One-Way Functions by Noga Amit and Guy Rothblum
See my comments.

[Jad at the theory seminar of WIS, 27 Dec 2023] (RnC)
Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions by Ronen Shaltiel and Jad Silbak by
See my comments.

[Eliran at the TOC seminar of Weizmann, 5 Feb 2024]
Conflict Checkable and Decodable Codes and Their Applications by Benny Applebaum and Eliran Kachlon
See my comments.

[Ronitt at the TOC seminar of Weizmann, 19 February 2024] (PT)
Properly learning monotone functions via local correction by Jane Lange, Ronitt Rubinfeld and Arsen Vasilyan
See my comments.

[Seen on ECCC, 18-Aug-2023 (but waited for a revision till 1-Mar-2024)] (PT)
Distribution-Free Proofs of Proximity by Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron Rothblum
See my comments.

[Algorithms meeting at Weizmann, 14-Mar-2024]
Faster Combinatorial Algorithms for Bipartite Matching by Julia Chuzhoy and Sanjeev Khanna.
See my comments.

[Happened to see it (late), 21-Mar-2024] (PT)
Estimating the Effective Support Size in Constant Query Complexity by Shyam Narayanan and Jakub Tetek
See my comments.

[Nathan at Weizmanan's theorylunch, 17-Apr-2024] (CT)
Worst-Case to Expander-Case Reductions: Derandomized and Generalized by Amir Abboud and Nathan Wallheimer
See my comments.

[found in a search, 28 April 2024] (RnC)
Expander Decomposition and Pruning: Faster, Stronger, and Simpler by Thatchaphol Saranurak and Di Wang
See my comments.

[Yotam at the WIS theory seminar, 6th May 2024] (CT)
New Derandomized Agreement Tests by Yotam Dikstein, Irit Dinur, and Alex Lubotzky.
See my comments.

[Seen on PTreview, 12 May 2024.] (PT)
Testing Ck-freeness in bounded-arboricity graphs by Talya Eden, Reut Levi, Dana Ron
See my comments.

[Seen in ECCC, 20 May 2024] (PT/PPS)
Interactive Proofs for General Distribution Properties by Tal Herman and Guy Rothblum
See my comments.

[Seen in ECCC, 27 May 2024] (CT/CRY)
A Note on Zero-Knowledge for NP and One-Way Functions by Yanyi Liu, Noam Mazor, and Rafael Pass.
See my comments.

[Seen in ECCC, 31 May 2024] (PRG)
Near-Optimal Averaging Samplers by Zhiyang Xun and David Zuckerman
See my comments.

[MFO, 3-7 June 2024] (CT)
Some highlights of the Oberwolfach complexity workshop
A partial list includes
* Raghu Meka - Structure vs Randomness Redux: New Frontiers and Applications
* Amir Abboud - Recent Developments in Fine-Grained Complexity
* Avi Wigderson - Reading Turing’s Papers
* Pranjal Dutta - Recent Advances in Polynomial Identity Testing
* Venkatesan Guruswami - 3-query LCC
* Ron Rothblum - Batch Verification
* Pravesh Kothari - Spectral Refutation for Semirandom CSPs and Applications to Local Codes
* Shuichi Hirahara - One-Way Functions and Zero Knowledge
* Venkatesan Guruswami - The Parameterized Inapproximability Hypothesis
* Shafi Goldwasser -- Verification of ML
* Xin Li - Recent Developments in the Theory of Randomness Extractors
See my comments.

[WIS's TOC seminar, 10 June 2024] (RnC)
Fast and Cheap Asynchronous Construction of Small $k$-Dominating Sets by Yuval Emek
See my comments.

[BU, 10-11 July 2024] (CT)
Some highlights of the LevinFest
* Eric Allender - The Minimum Circuit Size Problem through the Ages
* Levin's comment on Oded Goldreich's talk (Pseudorandom Generators)
* Igor Carboni Oliveira - Levin Complexity and Pseudodeterministic Constructions of Primes
* Leonid Levin - Set Theory in the Foundation of Math: Internal Classes, External Sets
* Madhu Sudan - Universality in Communication
See my comments.

[Pointed out by Dana, 5 August 2024] (PT)
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas by Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
See my comments.

[Pointed out by Dana, 6 August 2024] (PT)
Testing versus estimation of graph properties, revisited by Lior Gishboliner, Nick Kushnir, Asaf Shapira.
See my comments.

[Partially attended, 5-7 August 2024] (PT)
Workshop on Local Algorithms (chaired by Clement Canonne)
See my comments.

Go to the top of this page. Back to Oded Goldreich's homepage.