Go to the most recent choice.

My problem with many of these blogs is that they tend to cover the obvious (i.e., they all focus more or less on the same "hot results" that draw everybody's attention). I would like to contribute to the project of regaining forums devoted to the presentation of ideas in a different way; specifically, by calling attention to works that have facsinated me although they were not necessarily labeled as "hot".

Needless to say, my choices will be restricted to my own research areas, and even within these areas the choices will be confined to what I have heard and/or read (and understand well enough to write about...). Thus, the fact that a specific work is not mentioned does not indicate that I have a "not so high" opinion of this work; it may be the case that I do not know this work at all or that I don't know it well enough to feel comfortable writing about it or that I'm too preoccupied with something and neglect this new commitment. Lastly, let me note that my own works will not be included in my choices (to follow).

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

[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.

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