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
Preface
My impression is that STOC and FOCS do not function any more
as forums devoted to the presentation and exchange of ideas
(but rather function as "weight-lifting competitions"; see
more on this).
The question is what can be done to serve the need for the lost forums.
One answer is provided by various personal blogs in which various
researchers present their own choices of (relatively) recent works
that have drawn their attention.
[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).
[Omer at Shafi's Seminar, Jan. 22, 2009]
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]
A Counterexample to Strong Parallel Repetition
by Ran Raz
See my comments and the original abstract
[Kobbi at Shafi's Seminar, Feb. 5, 2009]
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?")
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]
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]
(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]
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]
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]
3-Query Locally Decodable Codes of Subexponential Length
by Klim Efremenko
See my comments and the original abstract
[Iftach, private discussion, March 2009]
A Parallel Repetition Theorem for Any Interactive Argument
by Iftach Haitner
See my comments and the original abstract
[reading, March 2009]
Are PCPs Inherent in Efficient Arguments?
by Guy Rothblum and Salil Vadhan
See my comments and the original abstract
[reading, March 2009]
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]
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]
[+ 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]
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]
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]
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]
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]
Testing Juntas Nearly Optimally
by Eric Blais
See my comments and the original abstract
[July 10, 2009]
Efficient Two-Sources Randomness Extraction:
A Challenge from the mid-1980s
See my comments
[Youming at Random'09, Aug. 21, 2009]
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]
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]
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].
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
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]
Update on Polynomial Identity Testing
by Amir Shpilka.
See my comments and the original abstract
[Zeev at MFO, Nov. 17, 2009]
Kakeya Sets and Extractors (survey)
by Zeev Dvir.
See my comments and the original abstract
[Les at MFO, Nov. 17, 2009]
Holographic Algorithms by Leslie Valiant.
See my comments and the original abstract
[Anup at MFO, Nov. 17, 2009]
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]
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]
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]
Complexity of CSPs: Exact and Approximation
by Prasad Raghavendra.
See my comments and the original abstract
[Ben at MFO, Nov. 20, 2009]
k-Clique on Random Graphs
by Ben Rossman.
See my comments and the original abstract
[Mark at MFO, Nov. 20, 2009]
Poly-logarithmic independence fools AC0 circuits
by Mark Braverman: .
See my comments and the original abstract
[Scott at MFO, Nov. 20, 2009]
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]
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]
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]
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]
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]
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]
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]
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]
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.)
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]
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]
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]
Cuckoo Nesting: Modern Methods for Organizing Lookup Tables.
by Moni Naor.
See my comments
[reading ECCC's TR10-072, May 2010]
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]
Greedy algorithms and why simple algorithms can be complex
by Allan Borodin
See my comments
[Email exposition by Mohammad, May 31, 2010]
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]
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]
IP = PSPACE using Error Correcting Codes
by Or Meir
See my comments
[Dana at RANDOM'10, Sept. 1, 2010]
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]
High-rate codes with sublinear-time decoding
by Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin.
See my comments
[Recommended by Avi, Oct. 5, 2010]
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]
The complexity of distributions
by Emanuele Viola
See my comments
[Private presentations by Or Meir, Nov. 2010]
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]
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]
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]
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]
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]
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.)
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]
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
See my comments
[Found on the web, Mar. 2, 2011]
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
by Gilad Asharov and Yehuda Lindell
See my comments and original abstract
[IHP, Paris, Mar. 25, 2011]
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]
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]
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]
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]
Determinant and Permanent (a survey talk)
by Avi Wigderson
See my comments
[Zvika in the Weizmann theory of computation seminar, June 15, 2011]
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]
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]
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]
On fourteen RANDOM/APPROX'11 Presentations (cf LNCS 6845)
See my comments
[Reading on ECCC, Sept 29, 2011]
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]
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]
Probabilistic Search Algorithms and their Cryptographic Applications
by Eran Gat and Shafi Goldwasser
See my comments
[Found on ECCC, Nov 2, 2011]
Characterizing Pseudoentropy
and Simplifying Pseudorandom Generator Constructions
by Salil Vadhan and Colin Jia Zheng
See my comments
[NYC Theory day, Nov 11, 2011]
Entropy-based Bounds on Dimension Reduction in L1
by Oded Regev
See my comments
[Seminar announcement in UCB, Nov 28, 2011]
Breaking the Coppersmith-Winograd Barrier
by Virginia Vassilevska Williams
See my comments
[Seen on ECCC, Dec 7, 2011]
Restriction Access
by Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff
See my comments
[Private presentation by Avi W., Feb 15, 2012]
High-Confidence Predictions under Adversarial Uncertainty
by Andrew Drucker
See my comments
[TCC'12, March 19-21, 2012]
Open Problems and Useful Observations
by various speakers at TCC'12
See my comments
[April 2, 2012]
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]
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]
Time Hierarchies for Sampling Distributions
by Thomas Watson
See my comments
[Seen on ECCC, TR12-043, April 20, 2012]
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]
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]
DNF Sparsification and a Faster Deterministic Counting
by Parikshit Gopalan, Raghu Meka, and Omer Reingold
See my comments
[Referred to by Or, May 2012]
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]
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