my choices [Oded Goldreich, started 2009]

RSS feed

Go to the most recent choice.

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.

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.


The choices


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



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