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.
Warning and request: Unfortunately, my comments contain lots of typos and various other errors. Please don't hesitate calling my attention to such cases.
[Editorial decisions.]
Initial policy: Include only works that I heard or read after Jan. 1, 2009.
Feb. 22, 2009: Include also surveys
(see the 1st such case).
Mar. 8, 2009: Include "double features"
(see the 1st such case).
Jul. 10, 2009: Include also highlights on open problems
(see the 1st such case).
Jan. 15, 2010: Include also overall accounts of workshops and/or conferences
(see the 1st such case).
March 2010: Revising the web-page format - moving my comments
(and the original abstracts) to separate pages.
[See old version.]
May 16, 2012: Include also useful observations decoupled from the work
in which they appear (see the 1st such case).
July 26, 2012: Include also old ideas that I regret not having known before
(see the 1st such case).
March 28, 2013: Adding general terms.
Sept 9, 2013: Annotating the RSS items
(starting from Nr. 137).
Legend for General Terms (indicated in the choice's time+location line): CRY = Cryptography, CT = Complexity Theory, EXT = (Randomness) Extractors, PPS = Probabilistic Proof Systems, PRG = Pseudorandomness, PT = Property Testing, RnC = Randomness and Computation. I tried to pick only one term per entry, although there is an obvious overlap between these terms.
[Omer at Shafi's Seminar, Jan. 22, 2009] (PRG)
Accessible Entropy (tentative title)
by Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee.
See my comments and the original abstract
[Ran in the WIS Theory Seminar, Feb. 1, 2009] (PPS)
A Counterexample to Strong Parallel Repetition
by Ran Raz
See my comments and the original abstract
[Kobbi at Shafi's Seminar, Feb. 5, 2009] (CRY)
What Can We Learn Privately?
by Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim,
Sofya Raskhodnikova, and Adam Smith.
See my comments and the original abstract
[Private presentation by Or Meir, Feb. 12, 2009]
(Avi: "Shame on you, did you not know it?") (CT)
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
by Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson
See my comments and the original abstract
[Dieter at the WIS Theory Seminar, Feb. 22, 2009] (CT)
Lower Bounds for Satisfiability and Related Problems (a survey)
by Dieter van Melkebeek
See my comments and the original abstract
[Avi at the WIS Theory Seminar, March 8, 2009]
[+ recall of a private presentation by Elazar, Dec. 25th 2008] (CT)
(1) Locally Testing Direct Product in the Low Error Range
by Irit Dinur and Elazar Goldenberg
(2) New Direct Product Code Testers, and PCPs
by Valentine Kabanets, Russell Impagliazzo, and Avi Wigderson
See my comments and the abstract of Avi's talk
[Tal at TCC'09, March 15, 2009] (CRY)
An Optimally Fair Coin Toss
by Tal Moran, Moni Naor, and Gil Segev.
See my comments and the original abstract
[Krzysztof at Weizmann's Theory Seminar, Mar. 22, 2009] (RnC)
Sublinear Graph Approximation Algorithms
by Krzysztof Onak, based on joint works
with Noga Alon, Avinatan Hassidim, Jonathan A. Kelner,
Philip N. Klein, and Huy N. Nguyen.
See my comments and the talk's abstract
[Klim at the WIS Theory Seminar, Mar. 29, 2009] (RnC)
3-Query Locally Decodable Codes of Subexponential Length
by Klim Efremenko
See my comments and the original abstract
[Iftach, private discussion, March 2009] (PPS)
A Parallel Repetition Theorem for Any Interactive Argument
by Iftach Haitner
See my comments and the original abstract
[reading, March 2009] (PPS)
Are PCPs Inherent in Efficient Arguments?
by Guy Rothblum and Salil Vadhan
See my comments and the original abstract
[reading, March 2009] (CT)
Worst-Case Running Times for Average-Case Algorithms
by L. Antunes and L. Fortnow
See my comments and the original abstract
[reading + private discussions with the authors, April 2009] (PPS)
Composition of low-error 2-query PCPs using decodable PCPs
by Irit Dinur and Prahladh Harsha
See my comments and the original abstract
[presentation in Eurocrypt'09, Apr. 27, 2009] (CRY)
[+ a recall from announcement at TCC'09, Mar. 16, 2007]
Two recent works on resettable security by Vipul Goyal and Amit Sahai:
(1) Resettably Secure Computation,
presented at Eurocrypt'09.
(2) Resolving the simultaneous Resettability Conjecture,
announced at the rump session of TCC'09.
See my comments and the original abstracts
[email exchange with Rafail, May 2009; following announcement at TCC'09]
(CRY)
Two recent works justifying various features of known zero-knowledge protocols.
(1) On the Composition of Public-Coin Zero-Knowledge Protocols,
by Rafael Pass, Wei-Lung Dustin Tseng, and Douglas Wikstrum.
(2) On Public versus Private Coins in Zero-knowledge Proof Systems,
by Rafael Pass and Muthuramakrishnan Venkitasubramaniam.
See my comments and the original abstracts
[Per at STOC'09, June 1, 2009] (CT)
Randomly supported independence and resistance
by Per Austrin and Johan Hastad
See my comments and the original abstract
[talk at STOC'09, June 1, 2009] (RnC)
Twice-Ramanujan Sparsifiers
by Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava
See my comments and the original abstract
[two talks at STOC'09, May 31, 2009] (CRY)
Two related works on non-malleable commitments (NMCs).
(1) Non-Malleability Amplification
by Huijia Lin and Rafael Pass
(2) A Unified Framework for Concurrent Security: Universal Composability
from Stand-alone Non-malleability
by Huijia Lin and Rafael Pass and Muthuramakrishnan Venkitasubramaniam
See my comments and the original abstracts
[Eric at STOC'09, May 31, 2009] (PT)
Testing Juntas Nearly Optimally
by Eric Blais
See my comments and the original abstract
[July 10, 2009]
(EXT)
Efficient Two-Sources Randomness Extraction:
A Challenge from the mid-1980s
See my comments
[Youming at Random'09, Aug. 21, 2009] (CT)
On the Security of Goldreich's One-Way Function
by Andrej Bogdanov and Youming Qiao.
See my comments and the original abstract
[Shachar at Random'09, Aug. 21, 2009] (CT)
Random low degree polynomials are hard to approximate
by Ido Ben Eliezer, Rani Hod and Shachar Lovett.
See my comments and the original abstract
[Jeff at Random'09, Aug. 23, 2009] (CT)
Pseudorandom Generators and Typically-Correct Derandomization
by Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel.
See my comments and the original abstract
[Nina at the Barriers in Computational Complexity workshop, Aug. 28, 2009].
(RnC)
Approximate Clustering without the Approximation
by Maria-Florina (Nina) Balcan
[Based mainly on works with Avrim Blum, Anupam Gupta, and Santosh Vempala]
See my comments and the original abstract
[Eden at the WIS theory Seminar, Nov. 8, 2009]
New Approximation Algorithms for Densest k-Subgraph (RnC)
by Aditya Bhaskara, Moses Charikar, Eden Chlamtac,
Uriel Feige and Aravindan Vijayaraghavan.
See my comments and the original abstract
[Amir at MFO, Nov. 16, 2009] (CT)
Update on Polynomial Identity Testing
by Amir Shpilka.
See my comments and the original abstract
[Zeev at MFO, Nov. 17, 2009] (EXT)
Kakeya Sets and Extractors (survey)
by Zeev Dvir.
See my comments and the original abstract
[Les at MFO, Nov. 17, 2009] (CT)
Holographic Algorithms by Leslie Valiant.
See my comments and the original abstract
[Anup at MFO, Nov. 17, 2009] (CT)
Direct Sums in Randomized Communication Complexity
by Boaz Barak, Mark Braverman,
Anup Rao and Xi Chen.
See my comments and the original abstract
[Chris at MFO, Nov. 18, 2009] (RnC)
Fast polynomial factorization and modular composition
by Kiran Kedlaya and Chris Umans
See my comments and the original abstract
[Omer at MFO, Nov. 18, 2009] (PRG)
Going down HILL: Efficiency Improvements
for Constructions of PRG from any OWF
by Iftach Haitner, Omer Reingold and Salil Vadhan.
See my comments and the original abstract
[Prasad at MFO, Nov. 19, 2009] (CT)
Complexity of CSPs: Exact and Approximation
by Prasad Raghavendra.
See my comments and the original abstract
[Ben at MFO, Nov. 20, 2009] (CT)
k-Clique on Random Graphs
by Ben Rossman.
See my comments and the original abstract
[Mark at MFO, Nov. 20, 2009] (PRG)
Poly-logarithmic independence fools AC0 circuits
by Mark Braverman.
See my comments and the original abstract
[Scott at MFO, Nov. 20, 2009] (CT)
Efficient Simulation of Quantum Mechanics Collapses the Polynomial Hierarchy
by Scott Aaronson.
See my comments and the original abstract
[Shiri at the WIS Theory Seminar, Nov. 22, 2009] (RnC)
Fault-Tolerant Spanners for General Graphs
by
Shiri Chechik, Michael Langberg, David Peleg and Liam Roditty.
See my comments and the original abstract
[Benny at the WIS Theory Seminar, Dec. 6, 2009] (PRG)
Cryptography by Cellular Automata
or How Fast Can Complexity Emerge in Nature?
by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz.
See my comments and the original abstract
[ITCS, Tsinghua University, Beijing, Jan. 8-10, 2010] (PT)
The ITCS mini-workshop on Property Testing, January 2010
See the workshop's abstract and
an annotated program of the workshop.
The following three choices are taken from this program.
[Rocco at the ITCS mini-workshop on Property Testing, Jan. 8, 2010] (PT)
Testing by Implicit Learning (survey)
by Rocco Servedio.
See my comments and the original abstract
[Madhu at the ITCS mini-workshop on Property Testing, Jan. 9, 2010] (PT)
Invariance in Property testing (survey)
by Madhu Sudan.
See my comments and the original abstract
[Shubhangi at the ITCS mini-workshop on Property Testing, Jan. 10, 2010] (PT)
Some recent results on testing of sparse linear codes
by Swastik Kopparty and Shubhangi Saraf.
See my comments and the original abstract
[ETH, Zurich, Feb. 9-11, 2010] (CRY)
The 7th Theory of Cryptography Conference (TCC), February 2010
See my notes regarding ten talks
presented in this conference (see list).
[private presentation of Zvika (Brakerski), Mar. 14, 2010] (CRY)
Two related works on Oblivious RAMs:
(1) Oblivious RAMs without Cryptographic Assumptions
by Ajtai.
(2) Perfectly Secure Oblivious RAM Without Random Oracles
by Damgard, Meldgaard, and Nielsen.
See my comments and the original abstracts
[scanning the FOCS'09 proceedings, March 2010]
(better late than never.) (RnC)
Needless to say, the following works are unrelated.
(1) Faster Generation of Random Spanning Trees
by Jonathan A. Kelner and Aleksander Madry.
(2) Constructing Small-Bias Sets from Algebraic-Geometric Codes
by Avraham Ben-Aroya and Amnon Ta-Shma.
(3) A Probabilistic Inequality with Applications to Threshold
Direct-Product Theorems by Falk Unger.
(4) A Complete Characterization of Statistical Query Learning with
Applications to Evolvability by Vitaly Feldman.
Note: a handful of other works are covered by previous choices.
See my comments
[Or at WIS's Theory Seminar, March 28, 2010] (PPS)
Derandomized Parallel Repetition of Structured PCPs
by Irit Dinur and Or Meir
See my comments and the original abstract
[Private presentation by Benny, April 25, 2010] (CRY)
Public-Key Encryption Schemes from Different Assumptions
by Benny Applebaum, Boaz Barak and Avi Wigderson.
See my comments and the original abstract
[Moni at the MTA lecture in memory of Shimon Even, May 5, 2010] (RnC)
Cuckoo Nesting: Modern Methods for Organizing Lookup Tables.
by Moni Naor.
See my comments
[reading ECCC's TR10-072, May 2010] (RnC)
Constructive Proofs of Concentration Bounds
by Russell Impagliazzo and Valentine Kabanets.
See my comments
[Allan at a conference marking Joachim von zur Gathen's 60th birthday,
May 28, 2010] (CT)
Greedy algorithms and why simple algorithms can be complex
by Allan Borodin
See my comments
[Email exposition by Mohammad, May 31, 2010] (CT)
On the Power of Randomized Reductions and the Checkability of SAT
by Mohammad Mahmoody and David Xiao
See my comments
[Reading from the CCC'10 proceedings, June 23, 2010] (CT)
The program-enumeration bottleneck in average-case complexity theory
by Luca Trevisan
See my comments
[Expositions by Or (+ reading a draft of the paper), Aug. 29, 2010] (PPS)
IP = PSPACE using Error Correcting Codes
by Or Meir
See my comments
[Dana at RANDOM'10, Sept. 1, 2010] (PT)
Distribution-Free Testing Algorithms for Monomials
with a Sublinear Number of Queries
by Elya Dolev and Dana Ron.
See my comments
[Recommended by Madhu, Sept. 24, 2010]
[Swastik at the WIS Theory Seminar, July 11, 2011] (RnC)
High-rate codes with sublinear-time decoding
by Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin.
See my comments
[Recommended by Avi, Oct. 5, 2010] (CT)
NP-Hardness of Approximately Solving Linear Equations Over Reals
by Subhash Khot and Dana Moshkovitz.
See my comments
[Scanning FOCS'10 papers, Oct. 28, 2010] (CT)
The complexity of distributions
by Emanuele Viola
See my comments
[Private presentations by Or Meir, Nov. 2010] (CT)
Two papers by Ryan Williams
(1) Improving Exhaustive Search Implies Superpolynomial Lower Bounds
(2) Non-Uniform ACC Circuit Lower Bounds
See my comments,
which is the main resason for posting a
choice of this celebrated entry.
[Shai in the Weizmann theory seminar, Nov. 15, 2010] (CRY)
Fully Homomorphic Encryption over the Integers
by Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan.
See my comments and original abstract
[Yuri in the Weizmann theory seminar, Nov. 29, 2010] (RnC)
Triangular Rank and Dimension Reduction for $L_1$ Metrics
by Ilan Newman and Yuri Rabinovich
See my comments and original abstract
[Artur in the Weizmann theory seminar, Dec. 6, 2010] (PT)
Testing properties in arbitrary planar graphs via random walks
by Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler.
See my comments and original abstract
[ECCC posting, Nov. 2010] (PT)
Two related papers by Gregory Valiant and Paul Valiant:
(1) A CLT and tight lower bounds for estimating entropy
(2) Estimating the unseen: A sublinear-sample canonical estimator
of distributions
See my comments and original abstract
[Guy in the Weizmann theory seminar, Dec. 19, 2010] (CRY)
Boosting and Differential Privacy
by Cynthia Dwork, Guy Rothblum, and Salil Vadhan.
See my comments and original abstract
[Benny in the Weizmann theory seminar, Jan. 24, 2011]
(Indeed, I got some previews, months ago.) (PRG)
Pseudorandom Generators with Long Stretch and Low Locality from
Random Local One-Way Functions by Benny Applebaum
See my comments and original abstract
[Foundations and Trends in TCS, Vol.~5, Issue 3-4, 2010] (CT)
Arithmetic Circuits: A survey of recent results and open questions
by Amir Shpilka and Amir Yehudayoff
See my comments and original abstract
[Feb 21, 2011]
Open Problem: Good Locally Testable Codes - constant in all parameters
(PT)
See my comments
[Found on the web, Mar. 2, 2011] (PT)
Property Testing Lower Bounds Via Communication Complexity
by Eric Blais, Joshua Brody, and Kevin Matulef
See my comments and original abstract
[From ECCC, Mar. 17, 2011]
A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty
Computation (CRY)
by Gilad Asharov and Yehuda Lindell
See my comments and original abstract
[IHP, Paris, Mar. 25, 2011] (RnC)
Expander graphs: applications and constructions
(a mini-course of 3 lectures)
by Avi Wigderson
See my comments and pointer to slides
[Private presentation by Guy, Mar. 27, 2011] (CRY)
A Multiplicative Weights Mechanism for Interactive
Privacy-Preserving Data Analysis
by Moritz Hardt and Guy Rothblum
See my comments and the original abstract
[Brown U., March 28-30, 2011] (CRY)
Comments on Fifteen TCC'11 Presentations
(LNCS 6597)
See my comments
[Shiri Chechik in the Weizmann theory group meeting, May 11, 2011]
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
by Virginia Vassilevska Williams and Ryan Williams
See my comments
[Bertinoro, May 23-27, 2011] (PT)
Highlights of the Bertinoro Workshop on Sublinear Algorithms
(see workshop's webpage):
* Optimal O(1)-time approximations of bounded-degree CSPs
by Yuichi Yoshida
* Learning and testing k-modal distributions
by Rocco Servedio (et al)
These two talks as well as twenty additional ones are briefly
reviewed in my comments
[Avi in the Weizmann theory of computation seminar, June 6, 2011] (CT)
Determinant and Permanent (a survey talk)
by Avi Wigderson
See my comments
[Zvika in the Weizmann theory of computation seminar, June 15, 2011] (CRY)
Efficient Fully Homomorphic Encryption from (Standard) LWE
by Zvika Brakerski and Vinod Vaikuntanathan.
See my comments
[Prahladh in the Weizmann theory of computation seminar, June 20, 2011] (CT)
Almost Settling the Hardness of Noncommutative Determinant
by Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan
See my comments
[Omer in the Weizmann theory of computation lunch, June 22, 2011] (RnC)
Balls and Bins: Smaller Hash Families and Faster Evaluation
by Laura Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder
See my comments
[Princeton U., August 17-19, 2011] (RnC)
On fourteen RANDOM/APPROX'11 Presentations (cf LNCS 6845)
See my comments
[Reading on ECCC, Sept 29, 2011] (PT)
Testing and Reconstruction of Lipschitz Functions with Applications
to Data Privacy
by Madhav Jha and Sofya Raskhodnikova
See my comments
[Recalling a discussion with Benny, Oct 12, 2011] (PRG)
A Dichotomy for Local Small-Bias Generators
by Benny Applebaum, Andrej Bogdanov, and Alon Rosen
See my comments
[Recalling a discussion with Shafi, Oct 12, 2011] (RnC)
Probabilistic Search Algorithms and their Cryptographic Applications
by Eran Gat and Shafi Goldwasser
See my comments
[Found on ECCC, Nov 2, 2011] (PRG)
Characterizing Pseudoentropy
and Simplifying Pseudorandom Generator Constructions
by Salil Vadhan and Colin Jia Zheng
See my comments
[NYC Theory day, Nov 11, 2011] (RnC)
Entropy-based Bounds on Dimension Reduction in L1
by Oded Regev
See my comments
[Seminar announcement in UCB, Nov 28, 2011] (CT)
Breaking the Coppersmith-Winograd Barrier
by Virginia Vassilevska Williams
See my comments
[Seen on ECCC, Dec 7, 2011] (CT)
Restriction Access
by Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff
See my comments
[Private presentation by Avi W., Feb 15, 2012] (RnC)
High-Confidence Predictions under Adversarial Uncertainty
by Andrew Drucker
See my comments
[TCC'12, March 19-21, 2012] (CRY)
Open Problems and Useful Observations
by various speakers at TCC'12
See my comments
[April 2, 2012] (PRG)
Approximating the Number of Satisfying Assignments in DNFs:
A Derandomization Challenge from the early-1990s
See my comments
[Seen on ECCC, TR12-034, April 9, 2012] (RnC)
New Lower Bounds for Matching Vector Codes
by Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett.
See my comments
[Seen on ECCC, TR12-026, April 15, 2012] (CT)
Time Hierarchies for Sampling Distributions
by Thomas Watson
See my comments
[Seen on ECCC, TR12-043, April 20, 2012] (RnC)
Efficient Interactive Coding Against Adversarial Noise
by Zvika Brakerski and Yael Tauman Kalai
See my comments
[NYC Theory day, May 4, 2012]
Four talks at NYC Theory day
by Michael Kearns (on Experiments in Social Computation),
Eli Ben-Sasson
(on An Additive Combinatorics Approach to the Log-rank Conjecture),
Aleksander Madry (on Online Algorithms and the K-server Conjecture),
and Shubhangi Saraf (on The Method of Multiplicities).
See my comments
[A late notice of ECCC TR10-144, May 5, 2012] (EXT)
From Affine to Two-Source Extractors via Approximate Duality
by Eli Ben-Sasson and Noga Zewi
See my comments
[Seen on ECCC, TR12-060, May 15, 2012] (PRG)
DNF Sparsification and a Faster Deterministic Counting
by Parikshit Gopalan, Raghu Meka, and Omer Reingold
See my comments
[Referred to by Or, May 2012] (PPS)
An observation regarding the construction of practical
probabilistic proof systems taken from the work
On the Concrete-Efficiency Threshold of Probabilistically-Checkable
Proofs by Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin,
and Eran Tromer (ECCC TR12-045).
See my comments
[Heard in STOC'12, May 20, 2012] (CT)
Two works regarding the Unique Games (UG) Conjecture
(1) A new point of NP-hardness for Unique Games
by Ryan O'Donnell, John Wright
(2) Hypercontractivity, Sum-of-Squares Proofs, and their Applications
by Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
See my comments
[Missed in STOC'12, found on ECCC; May 21, 2012] (CT)
Interactive Information Complexity by Mark Braverman.
See my comments
[Heard in STOC'12, May 21, 2012]
Three exciting algorithmic works
(1) Routing in Undirected Graphs with Constant Congestion
by Julia Chuzhoy
(2) Improving Chrisofides' Algorithm for the s-t Path TSP
by Hyung-Chan An, Robert Kleinberg, David B. Shmoys
(3) Multiplying Matrices Faster Than Coppersmith-Winograd
by Virginia Vassilevska Williams
See my comments
[Referred to by Or, June 20th, 2012] (PRG)
Pseudorandomness from Shrinkage
by Russell Impagliazzo, Raghu Meka, and David Zuckerman
See my comments, which offer a restricted
perspective on their work; referring to the (in)sensitivity of
some ``space fooling'' PRGs to the order in which their output bits
are presented (the current work that refers top the Nisan-Zuckerman PRG
is constrasted with known results regarding Nisan's PRG).
[In CCC'12, referred to by Or, July 7th, 2012] (RnC)
Share Conversion and Private Information Retrieval
by Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov
See my comments.
[Pointed out by Avi, July 23, 2012] (CT)
On simple functions, non-determinism, and depth-three circuits
by Les Valiant (1977 and 1983).
See my comments.
[Pointed out by Or, July 22, 2012] (CT)
Every NL set has constant-depth Boolean circuits of sub-exponential
size (folklore?)
See my comments.
[MIT, Aug 15-17, 2012] (RnC)
A small sample of RANDOM+APPROX 2012 talks
[LNCS 7408]
See my comments.
[Seen on ECCC, Sept 13, 2012] (PRG)
A Derandomized Switching Lemma and an Improved Derandomization of AC0
by Luca Trevisan and TongKe Xuey.
See my comments.
[Seen on ECCC, Sept 25, 2012] (CT)
Proof vs. Truth in Computational Complexity by Boaz Barak.
See my comments.
[Seen on ECCC, Oct 11, 2012] (PRG)
Better pseudorandom generators from milder pseudorandom restrictions
by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan
See my comments.
[Email discussion with Rafi, Nov 5, 2012] (CRY)
How to Garble RAM Programs
by Steve Lu and Rafail Ostrovsky
See my comments.
[Seen on ECCC, Nov 15, 2012] (PT)
These two independent works on Conditional Samples in Distribution Testing:
(1) On the Power of Conditional Samples in Distribution Testing
by Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah
(2) Testing probability distributions using conditional samples
by Clement Canonne, Dana Ron, and Rocco Servedio
See my comments.
[Seen on ECCC, Nov 26, 2012] (PT)
Strong LTCs with inverse polylogarithmic rate and soundness
by Michael Viderman
See my comments.
[Guy at Weizmann's TOC seminar, Dec 31, 2012] (PPS)
Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
by Guy Rothblum, Salil Vadhan, and Avi Wigderson.
See my comments.
[Pointed out by Or, Jan 1, 2013] (CT)
Natural Proofs Versus Derandomization
by Ryan Williams
See my comments.
[Seen on ECCC, Feb 6, 2013] (PT)
Strong LTCs with inverse poly-log rate and constant soundness
by Michael Viderman
See my comments.
[Seen on ECCC, Feb 8, 2013] (EXT)
Extractors for a Constant Number of Independent
Sources with Polylogarithmic Min-Entropy
by Xin Li
See my comments.
[Seen on ECCC, Feb 19, 2013] (PT)
A ${o(n)}$ monotonicity tester for Boolean functions over the hypercube
by Deeparnab Chakrabarty and C. Seshadhri
See my comments.
[Tokyo, March 4-6, 2013] (CRY)
My choice of highlights from
the 10th Theory of Cryptography Conference (TCC) includes
1. A Counterexample to the Chain Rule for Conditional HILL Entropy
by S. Krenn, K. Pietrzak, and A. Wadia
2. Languages with Efficient Zero-Knowledge PCPs are in SZK
by M. Mahmoody and D. Xiao
3. Unprovable Security of Perfect NIZK
and Non-interactive Non-malleable Commitments by R. Pass
4. Invited Talk by Tal Malkin on Secure Computation for Big Data
5. Testing the Lipschitz Property over Product Distributions
with Applications to Data Privacy by K. Dixit, M. Jha,
S. Raskhodnikova, and A. Thakurta
6. Invited Talk by Benny Applebaum on
Cryptographic Hardness of Random Local Functions
See my comments regarding these talks
as well as a larger sample of TCC'13 talks.
[Private communication by Tom and Ron, Spring 2013] (PPS)/(PT)
Non-Interactive Proofs of Proximity
by Tom Gur and Ron Rothblum
See my comments.
[Seen in CC Vol 22-2 (missed at CCC'12), June 3rd, 2013] (RnC)
Is Valiant-Vazirani's Isolation Probability Improvable?
by Holger Dell, Valentine Kabanets, Dieter van Melkebeek, and Osamu Watanabe
See my comments, better late than never.
[Seen on ECCC, June 9th, 2013] (CT)
Communication is bounded by root of rank
by Shachar Lovett.
See my comments.
[Pointed out by Or, June 15, 2013] (RnC)
Local Correctability of Expander Codes
by Brett Hemenway, Rafail Ostrovsky, and Mary Wootters
See my comments.
[Jonathan in WIS's theory lunch, June 19, 2013] (CRY)
Answering $n^{2+o(1)}$ Counting Queries with Differential Privacy is
Hard
by Jonathan Ullman
See my comments.
[Dana's talk at a Property Testing workshop, June 18, 2013] (PT)
Exponentially improved algorithms and lower bounds for
testing signed majorities
by Dana Ron and Rocco Servedio
See my comments.
[Seen on ECCC, June 26, 2013] (PPS)
Constant rate PCPs for circuit-SAT with sublinear query complexity
by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir,
and Henning Stichtenoth
See my comments.
[Ron in WIS's theory lunch, June 26, 2013] (PPS)
Delegation for Bounded Space
by Yael Tauman Kalai, Ran Raz, and Ron Rothblum
See my comments.
[Reminded of Andrej's talk at WIS (in May 2010), June 29, 2013] (PT)
A better tester for bipartiteness?
by Andrej Bogdanov and Fan Li
See my comments, better late than never.
[Pointed out by Or, June 29, 2013] (RnC)
Constructing Hard Functions from Learning Algorithms
by Adam Klivans, Pravesh Kothari, and Igor Oliviera.
See Or's and Oded's comments.
[Pointed out by Or, June 29, 2013] (RnC)
Interactive Channel Capacity
by Gillat Kol and Ran Raz.
See my comments.
[Benny at the WIS theory seminar, July 1, 2013] (CRY)
Locally Computable Universal One-Way Hash Functions
with Linear Shrinkage
by Benny Applebaum and Yoni Moses
See my comments.
[Gilad at the WIS theory lunch, July 3, 2013] (PT)/(RnC)
Tight Approximation of Image Matching
by Simon Korman, Daniel Reichman, and Gilad Tsur
See my comments.
[A word of mouth, July 7, 2013] (PPS)/(CT)
Analytical Approach to Parallel Repetition
by Irit Dinur and David Steurer
See my comments.
[Seen on ECCC, July 18, 2013] (CT)
A Uniform Min-Max Theorem with Applications in Cryptography
by Salil Vadhan and Colin Jia Zheng
See my comments.
[Reminded by a talk at CTW (see Item 4), July 30, 2013] (CT)
Approximation Resistance from Pairwise Independent Subgroups
by Siu On Chan
See my comments.
[CTW, Aarhus, July 30, 2013] (RnC)
Some talks at the China Theory Week
1. Chenggang Wu: Testing Surface Area
2. Huy L. Nguyen:
Approximate Near Neighbor Search Beyond Locality Sensitive Hashing
3. Reut Levi:
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
4. Sangxia Huang:
Improved Hardness of Approximating Chromatic Number
5. Avishay Tal:
Properties and Applications of Boolean Function Composition
6. Zeyu Guo: Randomness-Efficient Curve Samplers
See my comments.
[Pointed out by Or, August 8, 2013] (CT)
Approximating Boolean functions with depth-2 circuits
by Eric Blais and Li-Yang Tan.
See my comments.
[Private communication by Ron, Fall 2012]
[(I waited for) ECCC posting, Aug 9, 2013] (CRY)
Efficient Multiparty Protocols via Log-Depth Threshold Formulae
by Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker,
Peter Bro Miltersen, Ran Raz, and Ron Rothblum
See my comments.
[Pointed out by Boaz, August 22, 2013] (CRY)
Two papers on Obfuscation, Non-Black-Box Simulation,
and Resettable Cryptography
by Nir Bitansky and Omer Paneth
1. From the Impossibility of Obfuscation
to a New Non-Black-Box Simulation Technique;
2. On the impossibility of approximate obfuscation and applications
to resettable cryptography
See my comments.
[Seen on ECCC, Aug 24, 2013] (PT)
Instance-by-instance optimal identity testing
by Gregory Valiant and Paul Valiant
See my comments.
[Pointed out by Boaz, Aug 27, 2013] (PT)
Candidate Indistinguishability Obfuscation
and Functional Encryption for all circuits
by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai,
and Brent Waters
See my comments.
[Discusson with Gil, Aug 31, 2013] (CT)
A taste of Circuit Complexity Pivoted at NEXP not in ACC0 (and more)
by Gil Cohen
See my comments.
[Seen on ECCC, Sept 3, 2013] (CT)
Algorithms versus Circuit Lower Bounds
by Igor Oliveira
See my comments.
[Mihir talk at GM-Fest, MIT, Sept 7, 2013] (CRY)
Instantiating Random Oracles via UCEs
by Mihir Bellare, Viet Tung Hoang, and Sriram Keelveedhi
See my comments.
[Email from Sesh, Sept 10, 2013] (PT)
The Property Testing Review Website
See details on this new site.
[Seen on ECCC, Sept 13, 2013] (CT)
Two works regarding the complexity of deciding properties
of sampleable distributions
by Thomas Watson
1. The Complexity of Estimating Min-Entropy, ECCC TR12-070.
2. The Complexity of Deciding Statistical Properties of
Samplable Distributions, ECCC TR13-124.
See my comments.
[Igor at WIS's TOC seminar, Nov 4, 2013]
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
by Itai Benjamini, Gil Cohen, and Igor Shinkar
See my comments.
[Seen on ECCC, Nov 20, 2013] (CT)
$(2+\epsilon)$-SAT is NP-hard
by Per Austrin, Venkatesan Guruswami, and Johan Hastad
See my comments.
[Weizmann Institute, Dec 10-12, 2013]
Celebration of the work of Shafi Goldwasser and Silvio Micali
featuring of a day of TOC lectures and a two-day workshop on theory of
cryptography.
See the event's website
and my comments
(which actually add nothing).
[Julia at WIS's TOC seminar, Dec 22, 2013]
Polynomial Bounds for the Grid-Minor Theorem
by Chandra Chekuri and Julia Chuzhoy
See my comments.
[Or at WIS's TOC seminar, Jan 6, 2014] (CT)
Toward Better Formula Lower Bounds:
An Information Complexity Approach to the KRW Composition Conjecture
by Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson.
See my comments.
[Private communication by Elazar and Igor, Fall 2013] (PT)
Direct Sum Testing
by Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar
See my comments.
[Dagstuhl, 16-21 March 2014] (CT)
Dagstuhl workshop on Computational Complexity of Discrete Problems
(a selection of twenty talks)
See my comments.
[Seen on ECCC, 11 April 2014] (CT)
Exponential Separation of Information and Communication
by Anat Ganor, Gillat Kol, and Ran Raz
See my comments.
[Found at random on arXiv, 30 April 2014] (CT)
On Uniform Reductions between Direct Product and XOR Lemmas
by Ragesh Jaiswal
See my comments.
[Theory lunch at Weizmann, 21 May 2014]
Hybrid Stretch and Sourcewise Spanners
by Merav Parter
See my comments.
[Pointed out by Roei Tell, 12 June 2014] (RnC)
Every locally characterized affine-invariant property is testable
by Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami,
and Shachar Lovett.
See my comments.
[Noticed on ECCC (three days too late), 27 July 2014] (RnC)
2-Server PIR with sub-polynomial communication
by Zeev Dvir and Sivakanth Gopi
See my comments.
[Seen on ECCC, 10 August 2014] (RnC)
Locally Correctable and Testable Codes Approaching the Singleton Bound
by Or Meir
See my comments.
[Seen on ECCC, 10 August 2014] (CT/CRY)
On Basing Size-Verifiable One-Way Functions on NP-Hardness
by Andrej Bogdanov and Christina Brzuska
See my comments.
[Seen on ECCC, 10 August 2014] (CT)
Noncommutative Determinant is Hard: A Simple Proof Using an
Extension of Barrington's Theorem
by Craig Gentry
See my comments.
[Seen on ECCC, 20 August 2014] (CT)
Separation between Estimation and Approximation
by Uriel Feige and Shlomo Jozeph.
See my comments.
[Seen on ECCC, 27 August 2014] (CT)
Exponential Separation of Information and Communication
for Boolean Functions
by Anat Ganor, Gillat Kol, and Ran Raz
See my comments.
[Seen in STOC'14 proceedings, 28 August 2014] (PT)
$L_p$-testing
by Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev.
See my comments.
[Barcelona, Sept 4-6 2014] (RnC)
One Approx'14 invited talk and eight Random'14 un-invited talks
See my comments.
[Philadelphia, October 19-21, 2014]
A few works from FOCS'14
(1) Preventing False Discovery in Interactive Data Analysis is Hard
by Moritz Hardt and Jonathan Ullman
(2) New algorithms and lower bounds for monotonicity testing
by Xi Chen, Rocco Servedio, and Li-Yang Tan
(3) Path-Finding Methods for Linear Programming:
Solving Linear Programs in tildeO(sqrt(rank)) Iterations
and Faster Algorithms for Maximum Flow
by Yin Tat Lee and Aaron Sidford
Additional works have appeared as prior choices.
See my comments.
[Benny at WIS's theory semianr, Nov 17 2014] (CRY)
Arithmetic Cryptography
by Benny Applebaum, Jonathan Avron, and Christina Brzuska.
See my comments.
[Seen on ECCC, Dec 8 2014] (RnC)
Communication with Imperfectly Shared Randomness
by Clement Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan.
See my comments.
[Seen on ECCC, Dec 8 2014] (PT)
A Chasm
Between Identity and Equivalence Testing with Conditional Queries
by Jayadev Acharya, Clement Canonne, and Gautam Kamath.
See my comments.
[Omer at Weizmann's theory seminar, Dec 15 2014] (RnC)
Guilt-Free Interactive Data Analysis: The Reusable Holdout
by Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer
Reingold, and Aaron Roth.
See my comments.
[Gil at a private meeting, Dec 25 2014] (EXT)
Zero-Fixing Extractors for Sub-Logarithmic Entropy
by Gil Cohen and Igor Shinkar
See my comments.
[Belatedly seen on ECCC, Dec 31 2014] (CT)
Satisfiability Allows No Nontrivial Sparsification
unless the Polynomial-Time Hierarchy Collapses
by Holger Dell and Dieter van Melkebeek.
See my comments.
[``Belatedly'' posted on ECCC, Jan 22 2015] (PT)
On Monotonicity Testing and Boolean Isoperimetric type Theorems
by Subhash Khot, Dor Minzer, and Muli Safra.
See my comments.
[Seen on ECCC, Feb 5 2015] (PT)
Explicit Strong LTCs with inverse poly-log rate and constant soundness
by Michael Viderman
See my comments.
[Seen on ECCC, March 9 2015] (EXT)
Three-Source Extractors for Polylogarithmic Min-Entropy
by Xin Li
See my comments.
[private presentation, March 19 2015] (CT)
Tight bounds on The Fourier Spectrum of AC0
by Avishay Tal
See my comments.
[Gil at WIS's theory seminar, March 23 2015] (EXT)
Local Correlation Breakers
and Applications to Mergers and Multi-Source Extractors
by Gil Cohen
See my comments.
[Robi at WIS's theory lunch, March 25 2015] (RnC)
The Sketching Complexity of Graph Cuts
by Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
See my comments.
[Nir at WIS's theory seminar, March 30 2015] (CT)
On the Cryptographic Hardness of Finding a Nash Equilibrium
by Nir Bitansky, Omer Paneth, and Alon Rosen
See my comments.
[Seen on ECCC, April 3 2015] (CRY)
Minimizing Locality of One-Way Functions via Semi-Private
Randomized Encodings
by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz
See my comments.
[Seen on ECCC, May 7 2015] (RnC)
A simple proof of the Isolation Lemma
by Noam Ta-Shma
See my comments.
[private presentation by Or, April-May 2015] (RnC)
High rate locally-correctable and locally-testable codes with
sub-polynomial query complexity
by Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf
See my comments.
[Seen on ECCC, May 23 2015] (PPS)
Polynomially Low Error PCPs with polyloglogn Queries
via Modular Composition by Irit Dinur, Prahladh Harsha, and Guy Kindler
See my comments.
[Seen on ECCC, June 1st 2015] (PT)
Trading query complexity for sample-based testing and
multi-testing scalability
by Eldar Fischer, Oded Lachish, and Yadu Vadusev
See my comments.
[Seen on ECCC, June 15th 2015] (EXT)
Two-Source Dispersers for Polylogarithmic Entropy
and Improved Ramsey Graphs by Gil Cohen
See my comments.
[Seen on ECCC, July 24th 2015] (EXT)
Explicit Two-Source Extractors and Resilient Functions
by Eshan Chattopadhyay and David Zuckerman
See my comments.
[Seen on ECCC, August 6th 2015] (EXT)
Improved Constructions of Two-Source Extractors
by Xin Li
See my comments.
[Seen on ECCC, Sept 2nd 2015] (EXT)
Explicit resilient functions matching Ajtai-Linial
by Raghu Meka
See my comments.
[Presentation by Amir Shpilka, Nov 17th 2015] (RnC)
Bipartite Perfect Matching is in quasi-NC
by Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
See my comments.
[Seen on ECCC, Nov 17th 2015] (EXT)
Non-Malleable Extractors - New Tools and Improved Constructions
by Gil Cohen
See my comments.
[Tomer at the ML and Statistic seminar of Weizmann, Dec 16th 2015]
The Computational Power of Optimization in Online Learning
by Elad Hazan and Tomer Koren
See my comments.
[Amir at the TOC seminar of Weizmann, Dec 28th 2015] (CT)
Hardness in P (an overview)
by Amir Abboud
See my comments.
[Johns Hopkins University, January 7-9, 2016] (PT)
Notes from the Sublinear Algorithms Workshop
See my comments.
[Seen on ECCC, February 5, 2016] (EXT)
Randomness Extraction in AC0 and with Small Locality
by Kuan Cheng and Xin Li
See my comments.
[Seen on ECCC, February 5, 2016] (CT)
Fast Learning Requires Good Memory: A Time-Space Lower Bound for
Parity Learning
by Ran Raz
See my comments.
[Weizmann's theory lunch, February 10, 2016] (CT)
The Power of Depth for Feedforward Neural Networks
by Ronen Eldan and Ohad Shamir
See my comments.
[Seen on ECCC, April 15, 2016] (CT)
Can PPAD Hardness be Based on Standard Cryptographic Assumptions?
by Alon Rosen, Gil Segev, and Ido Shahaf
See my comments.
[Finally posted on ECCC, April 17, 2016] (PPS)
Constant-Round Interactive Proofs for Delegating Computation
by Omer Reingold, Guy Rothblum, and Ron Rothblum
See my comments.
[Merav at WIS's theory seminar, May 2, 2016] (RnC)
MST in Log-Star Rounds of Congested Clique
by Mohsen Ghaffari and Merav Parter
See my comments.
[Seen on ECCC, May 9, 2016] (PT)
A New Approach for Testing Properties of Discrete Distributions
by Ilias Diakonikolas and Daniel Kane
See my comments.
[Stephen at Weizmann's TOC seminar, May 23, 2016] (RnC)
Beating CountSketch for Heavy Hitters in Insertion Streams
by Vladimir Braverman, Stephen Chestnut
Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David Woodruff
See my comments.
[Seen in the 48th STOC proceedings, June 24, 2016] (RnC)
Instance Optimal Learning of Discrete Distributions
by Gregory Valiant and Paul Valiant.
See my comments.
[Seen in the 48th STOC proceedings, June 24, 2016] (PT)
A Polynomial Lower Bound for Testing Monotonicity
by Aleksandrs Belovs and Eric Blais
See my comments.
[Seen in the 48th STOC proceedings, June 25, 2016] (PRG)
Algebraic Attacks against Random Local Functions
and Their Countermeasures
by Benny Applebaum and Shachar Lovett
See my comments.
[Seen on ECCC, July 18, 2016] (EXT)
Low-error two-source extractors for polynomial min-entropy
by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma.
See my comments.
[Suggested by Or Meir, July 18, 2016] (CT)
No occurrence obstructions in geometric complexity theory
by Peter Burgisser, Christian Ikenmeyer, and Greta Panova
See my comments.
[Suggested by Or Meir, August 2, 2016] (CT)
Improving the lower bound on size complexity of explicit functions
and some limitations on subsequent improvements
by Magnus Gausdal Find, Alexander Golovnev,
Edward Hirsch, Alexander Knop, and Alexander Kulikov.
See my comments.
[Seen on ECCC, August 25, 2016] (PT)
A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness
by Deeparnab Chakrabarty and C. Seshadhri
See my comments.
[Seen on ECCC and digested, August 29, 2016] (RnC)
Local Expanders
by Emanuele Viola and Avi Wigderson
See my comments.
[Approx'16, Paris, Sept 7, 2016] (CT)
Proving weak approximability without algorithms
by Ridwan Syed and Madhur Tulsiani
See my comments.
[Belatedly seen on ECCC, Sept 2016] (RnC)
Perfect Bipartite Matching in Pseudo-Deterministic RNC
by Shafi Goldwasser and Ofer Grossman
See my comments.
[MSR and MIT, Oct 2016] (RnC)
Brief report of the Workshop on Local Algorithms
featuring two surveys and five works.
See my report.
[Seen on ECCC, Oct. 28, 2016] (CT)
NP-hard sets are not sparse unless P=NP: An exposition of a
simple proof of Mahaney's Theorem, with applications
by Joshua Grochow
See my comments.
[Discussion with Zeev Dvir, Oct 2016] (CT)
On the non-rigidity of generating matrices of good codes
by Zeev Dvir (written by Oded).
See the actual text.
[Private presentation by Tom; posted on ECCC, Nov 2, 2016] (PT)
Alice and Bob Show Distribution Testing Lower Bounds
by Eric Blais, Clement Canonne, and Tom Gur
See my comments.
[Private presentation by Avishay; posted on ECCC, Nov 16, 2016] (CT)
Computing Requires Larger Formulas than Approximating
by Avishay Tal
See my comments.
[Julia at WIS's TOC seminar, Nov 27, 2016]
New Hardness Results for Routing on Disjoint Paths
by Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.
See my comments.
[Seen on ECCC, Dec 13, 2016] (RnC)
Pseudodeterministic Constructions in Subexponential Time
by Igor Carboni Oliveira amd Rahul Santhanam.
See my comments.
[Seen on ECCC, Dec 19, 2016] (PT)
A Characterization of Constant-Sample Testable Properties
by Eric Blais and Yuichi Yoshida.
See my comments.
[Amir at a special seminar at WIS, Jan 12, 2017] (CT)
Hardness in P (survey talk)
by Amir Abboud
See my comments.
[Seen on ECCC, Feb 8, 2017] (CT)
White-Box vs. Black-Box Complexity of Search Problems:
Ramsey and Graph Property Testing
by Ilan Komargodski, Moni Naor, and Eylon Yogev
See my comments.
[Posted on ECCC, Feb 28, 2017] (CT)
Average-Case Fine-Grained Hardness
by Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
See my comments.
[Posted on ECCC, Apr 9, 2017] (CRY)
Limits on Low-Degree Pseudorandom Generators
(Or: Sum-of-Squares Meets Program Obfuscation)
by Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh Kothari
See my comments.
[Received as a gift on Apr 19, 2017] (CRY)
Tutorials on the Foundations of Cryptography
edited by Yehuda Lindell
See my comments.
[Seen on ECCC, Apr 23, 2017] (PT)
Settling the query complexity of non-adaptive junta testing
by Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie
See my comments.
[Luca at the TOC seminar of WIS, Apr 24, 2017]
Some Simple Distributed Network Processes
by Luca Becchetti, Andrea Clementi, Pasin Manurangsi,
Emanuele Natale, Francesco Pasquale, Prasad Raghavendra,m
and Luca Trevisan.
See my comments.
[Posted on ECCC, May 11, 2017] (PT) (CT)
High dimensional expanders imply agreement expanders
by Irit Dinur and Tali Kaufman
See my comments.
[Pasin at WIS's TheoryLunch, May 24, 2017] (CT)
ETH-hardness of Approximating Densest k-Subgraph
by Pasin Manurangsi
See my comments.
[Seen on ECCC, June 1, 2017] (CRY)
Multi Collision Resistant Hash Functions and their Applications
by Itay Berman, Akshay Degwekar, Ron Rothblum,
and Prashant Nalini Vasudevan
See my comments.
[Montreal, June 19-23, 2017]
On the 49th STOC (and Theory Fest 2017).
The Highlights of my report include
* Explicit, Almost Optimal, Epsilon-Balanced Codes by Amnon Ta-Shma.
* Avi Wigderson: On the Nature and Future of ToC
* Competitive Distribution Estimation: Why is Good-Turing Good
by Alon Orlitsky
* Orna Kupferman: Examining classical graph-theory problems
from the viewpoint of formal-verification methods
* An Improved Distributed Algorithm for Maximal Independent Set
by Mohsen Ghaffari.
See my report.
[Rohit at WIS's TheoryLunch, July 10, 2017] (RnC)
Derandomizing Isolation Lemma: a geometric approach
by Stephen Fenner, Rohit Gurjar and Thomas Thierauf.
See my comments.
[Seen on ECCC, July 18, 2017] (CT)
Crossing the Logarithmic Barrier
for Dynamic Boolean Data Structure Lower Bounds
by Kasper Green Larsen, Omri Weinstein, and Huacheng Yu.
See my comments.
[Seen on ECCC, August 16, 2017] (CT)
The Direct Sum of Universal Relations
by Or Meir
See my comments.
[Seen on ECCC, Sept 8, 2017] (PT)
Two works related to testing uniformity of distributions
by Ilias Diakonikolas, Themis Gouleakis, Daniel Kane,
John Peebles, Eric Price, and Alistair Stewart
See my comments.
[a belated report, Oct 3, 2017] (CT)
Advances in quantified derandomization of constant-depth circuits
two works by Roei Tell
See my comments.
[Seen on ECCC, Oct 8, 2017] (CT) (RnC)
Prediction from Partial Information and Hindsight,
with Application to Circuit Lower Bounds
by Or Meir and Avi Wigderson
See my comments.
[Seen on
PTreview, Oct 10, 2017] (PT)
Efficient Removal without Efficient Regularity
by Lior Gishboliner and Asaf Shapira
See my comments.
[Seen on
Roei's
expositions page, Oct 11, 2017] (CT)
Non-trivial derandomization implies weak lower bounds:
An exposition of an (almost) elementary proof
by Roei Tell
See my comments.
[Seen on ECCC, Oct 13, 2017] (PT)
Proofs of Proximity for Distribution Testing
by Alessandro Chiesa and Tom Gur
See my comments.
[Seen on ECCC, Nov 1, 2017] (PRG)
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
by Mark Braverman, Gil Cohen, and Sumegha Garg
See my comments.
[Seen on ECCC, Nov 1, 2017] (CRY)
From Laconic Zero-Knowledge to Public-Key Cryptography
by Itay Berman, Akshay Degwekar, Ron Rothblum, and Prashant Nalini Vasudevan
See my comments.
[ITCS'18 posted program, Nov 28, 2017]
A selection from the
ITCS'18
program.
* Pseudo-Deterministic Proofs
by Shafi Goldwasser, Ofer Grossman and Dhiraj Holden.
* Zero-Knowledge Proofs of Proximity
by Itay Berman, Ron Rothblum and Vinod Vaikuntanathan.
* Relaxed Locally Correctable Codes
by Tom Gur, Govind Ramnarayan and Ron Rothblum.
* Learning by Refuting
by Pravesh K Kothari and Roi Livni.
* Edge Estimation with Independent Set Oracles
by Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy,
Cyrus Rashtchian and Makrand Sinha.
* ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
by Irit Dinur and Pasin Manurangsi.
* Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
by Shay Solomon.
See my comments.
[Benny at the WIS complexity club, Nov 29, 2017] (CT)
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions
by Benny Applebaum
See my comments.
[Seen on ECCC, Dec 14, 2017] (CT)
Agreement tests on graphs and hypergraphs
by Irit Dinur, Yuval Filmus, and Prahladh Harsha
See my comments.
[Private presentation by Roei Tell, Dec 28, 2017] (CT)
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An
Easy Witness Lemma for NP and NQP
by Cody Murray and Ryan Williams
See my comments.
[Private presentation by Roei Tell, Dec 28, 2017] (CT)
Proving that prBPP=prP is as hard as ``almost'' proving that P neq NP
by Roei Tell
See my comments.
[Pointed out by Irit Dinur, Jan 10, 2018] (CT)
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion
by Subhash Khot, Dor Minzer, and Muli Safra
See my comments.
[Seen on ECCC, Jan 11, 2018] (PT)
A Generalized Turan Problem and its Applications
by Lior Gishboliner and Asaf Shapira
See my comments.
[Eylon at the WIS theory seminar, Jan 11, 2018] (CRY)
Distributed computing made secure: A new cycle cover theorem
by Merav Parter and Eylon Yogev
See my comments.
[Ofer at the WIS theory seminar, Jan 22, 2018] (RnC)
Reproducibility in Randomized Log-space
by Ofer Grossman and Yang Liu.
See my comments.
[Seen on ECCC, Feb 2, 2018] (PPS)
Efficient Batch Verification for UP
by Omer Reingold, Guy Rothblum, and Ron Rothblum
See my comments.
[Uri at WIS's Theory Lunch, March 14, 2018] (PT)
Approximate Modularity, Revisited
by Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen.
See my comments.
[Seen on ECCC, May 21, 2018] (PT)
Finding forbidden minors in sublinear time:
a $O(n^{1/2+o(1)})$-query one-sided tester
for minor closed properties on bounded degree graphs
by Akash Kumar, C. Seshadhri, and Andrew Stolman
See my comments.
[Seen on ECCC, June 9, 2018] (PRG)
Pseudorandom Generators for Width-3 Branching Programs
by Raghu Meka, Omer Reingold, and Avishay Tal
See my comments.
[Seen on ECCC, June 11, 2018] (PT)
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection
Sampling of Graphs by Amit Levi and Erik Waingarten.
See my comments.
[Seen on ECCC, June 25, 2018] (PRG)
A Tight Lower Bound for Entropy Flattening
by YiHsiu Chen, Mika Goos, Salil Vadhan, and Jiapeng Zhang
See my comments.
[Interaction with the authors, May-July 2018] (PPS/CRY)
An Efficiency-Preserving Transformation from Honest-Verifier Statistical
Zero-Knowledge to Statistical Zero-Knowledge
by Pavel Hubacek and Alon Rosen and Margarita Vald
See my comments.
[Recommended by Eric Blais, August 21, 2018] (PT)
Near log-convexity of measured heat in (discrete) time and consequences
by Mert Saglam
See my comments.
[Discussions with Roei, 27Sept-3Oct, 2018] (PRG)
Does the Choice of Expander Matter for Expander-Based One-way Function?
on a paper by Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell
See my comments.
[Oberwolfach, Nov 11-16, 2018] (CT)
Comments on some talks presented at a complexity workshop
See my comments.
[Seen on ECCC, Nov 25, 2018] (CT)
Bootstrapping Results for Threshold Circuits ``Just Beyond'' Known
Lower Bounds
by Lijie Chen and Roei Tell
See my comments.
[Julia at Weizmann's TOC seminar, Jan 7, 2019]
Almost polynomial hardness of node-disjoint paths in grids
by Julia Chuzhoy, David H.K. Kim, and Rachit Nimavat.
See my comments.
[ITCS, UCSD, Jan 10-11, 2019]
On a few works presented at ITCS'19
See my comments.
[Seen on ECCC, Jan 27, 2019] (PRG)
Sampling Graphs without Forbidden Subgraphs
and Almost-Explicit Unbalanced Expanders
by Benny Applebaum and Eliran Kachlon
See my comments.
[Eylon at WIS's theory seminar, Feb 4, 2019] (PPS)
The power of distributed verifiers in interactive proofs
Moni Naor, Merav Parter and Eylon Yogev
See my comments.
[posted on ECCC, Feb 26, 2019] (PPS)
Smooth and Strong PCPs by Orr Paradise
See my comments.
[talk in WIS's TOC seminar, Mar 25, 2019] (CRY)
Homomorphic Secret Sharing (survey) by Yuval Ishai
See my comments.
[seen on ECCC, Apr 1, 2019] (PT)
Random walks and forbidden minors II: A $\poly(d\eps^{-1})$-query
tester for minor-closed properties of bounded degree graphs
by Akash Kumar, C. Seshadhri, and Andrew Stolman
See my comments.
[Private presentation by Tal Herman, Apr 11, 2019] (RnC)
Statistical Difference Beyond the Polarizing Regime
by Itay Berman, Akshay Degwekar, Ron D. Rothblum,
and Prashant Nalini Vasudevan
See my comments.
[Posted on ECCC, Apr 14, 2019] (RnC)
A Lower Bound for Relaxed Locally Decodable Codes
by Tom Gur and Oded Lachish
See my comments.
[Got reminded of this posting, May 29, 2019] (CT)
Karp-Lipton theorems:
Translating non-uniform `collapses' into uniform `collapses'
(an exposition)
by Roei Tell
See my comments.
[Dana at WIS's TOC seminar, June 17, 2019] (CT)
Nearly Optimal Derandomization under Assumptions
by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
See my comments.
[Dylan at STOC'19, June 26, 2019] (CT)
Weak Lower Bounds on Resource-Bounded Compression
Imply Strong Separations of Complexity Classes
by Dylan McKay, Cody Murray, and Ryan Williams
See my comments.
[Phoenix, June 23-26, 2019]
On twelve STOC'19 presentations
(1) Bootstrapping Results for Threshold Circuits
Just Beyond Known Lower Bounds by Chen and Tell
(2) The Log-Approximate-Rank Conjecture is False
by Chattopadhyay, Mande, and Sherif
(3) Breaking Quadratic Time for Small Vertex Connectivity
and an Approximation Scheme
by Nanongkai, Saranurak, and Yingchareonthawornchai
(4) Distributed Edge Connectivity in Sublinear Time
by Daga, Henzinger, Nanongkai, and Saranurak
(5) Towards the Locality of Vizing's Theorem by Su and Vu
(6) Testing Graphs against an Unknown Distribution
by Gishboliner and Shapira
(7) Testing Unateness Nearly Optimally by Chen and Waingarten
(8) Random walks and forbidden minors II: a poly(d/epsilon)-query tester
for minor-closed properties of bounded degree graphs
by Kumar, Seshadhri, and Stolman
(9) Static Data Structure Lower Bounds Imply Rigidity
by Dvir, Golovnev, and Weinstein
(10) Solving Linear Programs in the Current Matrix Multiplication Time
by Cohen, Lee, and Song
(11) Sylvester-Gallai type theorems for quadratic polynomials
by Shpilka
(12) Weak Lower Bounds on Resource-Bounded Compression
Imply Strong Separations of Complexity Classes
by McKay, Murray, and Williams
See my comments.
[Partas, July 11, 2019]
On three ICALP'19 presentations
(1) Computing Optimal Epsilon-Nets Is as Easy as Finding
an Unhit Set by Nabil Mustafa
(2) Fine-Grained Complexity of Dynamic Programming Problems
(survey) by Karl Bringmann
(3) A Quest Towards Strong Unconditional Lower Bounds
(survey) by Kasper Green Larsen
See my comments.
[Zurich, July 20-22, 2019]
On the 3rd Workshop on Local Algorithms (WOLA'19)
See my comments.
[PapaFest, Columbia, Sept 6, 2019]
An Improved Approximation Algorithm for TSP in the Half Integral Case
by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan
See my comments.
[Private discussions with Zeev, Sept 13, 2019] (CT)
Fourier and Circulant Matrices Are Not Rigid
by Zeev Dvir and Allen Liu
See my comments.
[MIT, September 20-22, 2019]
On few presentation at the RANDOM'19 conference
See my comments.
[Theory Seminar of Columbia, Sept 25, 2019] (CT)
Lifting Lower Bounds, Communication, and Proofs
a survey talk by Toniann Pitassi
See my comments.
[Theory Seminar of Columbia, Sept 27, 2019] (PT)
Junta correlation is testable
by Anindya De, Elchanan Mossel, and Joe Neeman.
See my comments.
[Seen on ECCC, Oct 4, 2019] (PT)
Finding monotone patterns in sublinear time
by Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, and Erik Waingarten
See my comments.
[Seen on ECCC, Nov 5, 2019] (CT)
Optimal Inapproximability with Universal Factor Graphs
by Per Austrin, Jonah Brown-Cohen, and Johan Hastad
See my comments.
[Seen on ECCC, Nov 7, 2019] (PT)
Almost Optimal Testers for Concise Representations
by Nader Bshouty
See my comments.
[FOCS19, Nov 9th 2019]
Why I Am Excited About This Research Direction:
A Tribute to Shafi Goldwasser
by Madhu Sudan, Huijia (Rachel) Lin, Maria-Florina (Nina) Balcan,
and Ronitt Rubinfeld
See my comments.
[Baltimore, Nov 10-12th 2019]
A sample of FOCS19 presentations
(a partial list includes)
* Derandomization from Algebraic Hardness: Treading the Borders
by Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon
* Sampling Graphs without Forbidden Subgraphs
and Unbalanced Expanders with Negligible Error
by Benny Applebaum and Eliran Kachlon
* Lower bounds for maximal matchings and maximal independent sets
by Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti,
Mikal Rabie, and Jukka Suomela
* Efficient Construction of Rigid Matrices Using an NP Oracle
by Josh Alman and Lijie Chen
* Truly Optimal Euclidean Spanners
by Hung Le and Shay Solomon
* Hardness Magnification for all Sparse NP Languages
by Lijie Chen, Ce Jin, and Ryan Williams
* The Average-Case Complexity of Counting Cliques in Erdos-Renyi
Hypergraphs by Enric Boix-Adsera, Matthew Brennan, and Guy Bresler
* Non-deterministic Quasi-Polynomial Time is Average-case Hard
for ACC Circuits by Lijie Chen
* Agreement testing theorems on layered set systems
by Yotam Dikstein and Irit Dinur
* A characterization of graph properties testable for general planar graphs
with one-sided error (It's all about forbidden subgraphs)
by Artur Czumaj and Christian Sohler
See my comments.
[CU's Theory Seminar, Feb 18, 2020]
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
by Alexandr Andoni, Clifford Stein, and Peilin Zhong
See my comments.
[Got reminded, Feb 29th 2020] (CT)
High-precision estimation of random walks in small space
by AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles,
Aaron Sidford, and Salil Vadhan.
See my comments.
[Suggested by an anonymous friend, Mar 2nd 2020] (PT)
Testing Linear Inequalities of Subgraph Statistics
by Lior Gishboliner, Asaf Shapira, and Henrique Stagni.
See my comments.
[Seen on ECCC, Mar 22nd 2020]
Error Correcting Codes for Uncompressed Messages
by Ofer Grossman and Justin Holmgren.
See my comments.
[Discussion with Roei, April 2020] (CT)
On implications of better sub-exponential lower bounds for AC0
by Roei Tell
See my comments.
[Seen on ECCC, 26 April 2020] (PPS)
Interactive Proofs for Verifying Machine Learning
by Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff
See my comments.
[Seen on ECCC, 24 June 2020] (CT)
Is it possible to improve Yao's XOR lemma using reductions
that exploit the efficiency of their oracle?
by Ronen Shaltiel
See my comments.
[Seen on ECCC, 5 July 2020] (RnC)
Impossibility of Derandomizing the Isolation Lemma for all Families
by Manindra Agrawal, Rohit Gurjar, and Thomas Thierauf
See my comments.
[Seen on ECCC, 6 July 2020] (CT)
KRW Composition Theorems via Lifting
by Susanna de Rezende, Or Meir, Jakob Nordstrom,
Toniann Pitassi, and Robert Robere
See my comments.
[Seen on ECCC, 13 Sept 2020] (CT)
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
by William Hoza, Edward Pyne, and Salil Vadhan
See my comments.
[Seen on ECCC, 20 Sept 2020] (RnC)
Relaxed Locally Correctable Codes with Improved Parameters
by Vahid Reza Asadi and Igor Shinkar
See my comments.
[Seen on ECCC, 24 Sept 2020] (PPS)
Batch Verification for Statistical Zero Knowledge Proofs
by Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum,
and Adam Sealfon
See my comments.
[Seen on ECCC, 29 Sept 2020] (PRG)
Simple and Fast Derandomization from Very Hard functions:
Eliminating Randomness at Almost No Cost
by Lijie Chen and Roei Tell
See my comments.
[Seen on ECCC, 10 Oct 2020] (RnC)
A Structural Theorem for Local Algorithms
with Applications to Coding, Testing, and Privacy
by Marcel Dall'Agnol, Tom Gur, and Oded Lachish.
See my comments.
[Seen on ECCC, 29 Oct 2020] (PPS)
Batch Verification and Proofs of Proximity with Polylog Overhead
by Guy Rothblum and Ron Rothblum
See my comments.
[Seen on ECCC, 3 Dec 2020] (CT)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0
by Yuval Filmus, Or Meir, and Avishay Tal.
See my comments.
[Seen on ECCC, 30 Jan 2021] (PT)
Random walks and forbidden minors III:
poly(d/eps)-time partition oracles for minor-free graph classes
by Akash Kumar, C. Seshadhri, and Andrew Stolman.
See my comments.
[Seen on ECCC, 20 Feb 2020] (PRG)
Three works on pseudorandomness posted today
* Monotone
Branching Programs: Pseudorandomness and Circuit Complexity
by Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan
* Pseudodistributions
That Beat All Pseudorandom Generators
by Edward Pyne and Salil Vadhan
* Error
Reduction For Weighted PRGs Against Read Once Branching Programs
by Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma
See my comments.
[Seen on ECCC, 6 Mar 2021] (PPS)
Fiat-Shamir via List-Recoverable Codes
(or: Parallel Repetition of GMW is not Zero-Knowledge)
by Justin Holmgren, Alex Lombardi, and Ron Rothblum
See my comments.
[Seen on ECCC, 20 Mar 2021]
Promise Problems Meet Pseudodeterminism
by Peter Dixon, A. Pavan, and N.V. Vinodchandran
See my comments.
[Seen on ECCC, 27 Mar 2021] (PRG)
Better Pseudodistributions and Derandomization for Space-Bounded Computation
by William Hoza
See my comments.
[Seen on
PT review, 31 Mar 2021] (PT)
Testing Hamiltonicity (and other problems) in Minor-Free Graphs
by Reut Levi and Nadav Shoshan
See my comments.
[Seen in the CCC program, 1 June 2021] (PT)
GSF-locality is not sufficient for proximity-oblivious testing
by Isolde Adler, Noleen Kohler, and Pan Peng
See my comments.
[Seri at WIS's TheoryLunch, 9 June 2021]
Improved Hardness of Approximation for Distributed Diameter
by Ofer Grossman, Seri Khoury, and Ami Paz
See my comments.
[Private discussion with Roei, 10 June 2021] (CT)
Hardness vs Randomness, Revised:
Uniform, Non-Black-Box, and Instance-Wise
by Lijie Chen and Roei Tell
See my comments.
[Seen on ECCC, 15 June 2021] (CT)
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
by Nutan Limaye, Srikanth Srinivasan, and Sebastien Tavenas
See my comments.
[Seen on ECCC, 2 July 2021] (CT)
A Note on One-way Functions and Sparse Languages
by Yanyi Liu and Rafael Pass
See my comments.
[Reminded by Hila Dahari, 5 July 2021] (PPS)
On Prover-Efficient Public-Coin Emulation of Interactive Proofs
by Gal Arnon and Guy Rothblum
See my comments.
[Private presentation by Merav Parter, 19 and 21 July 2021]
Algebraic methods in the congested clique
by Keren Censor-Hillel, Petteri Kaski, Janne H.~Korhonen,
Christoph Lenzen, Ami Paz, and Jukka Suomela
See my comments.
[Private communication by Roei Tell, 7 August 2021] (CT)
On the feasibility of a seemingly
modest challenge in quantified derandomization
by Roei Tell
See my comments.
[Seen on ECCC, 20 August 2021] (CT)
How to Find Water in the Ocean: A Survey on Quantified Derandomization
by Roei Tell
See my comments.
[Seen on ECCC, 24 August 2021] (PT)
The complexity of testing all properties of planar graphs,
and the role of isomorphism
by Sabyasachi Basu, Akash Kumar, and C. Seshadhri
See my comments.
[Announcement of SI-TOC,
23 September 2021] (PT)
Locally Testable Codes with Constant Rate, Distance, and Locality
by Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes
See my comments.
[Amir at a faculty meeting at Weizmann, 1 December 2021]
Gomory-Hu Tree in Subcubic Time
by Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi,
Thatchaphol Saranurak, and Ohad Trabelsi
See my comments.
[Missed on ECCC but noticed today, 2 December 2021] (PT/PPS)
Sample-Based Proofs of Proximity
by Guy Goldberg and Guy Rothblum
See my comments.
[Pointed out by Dana Ron, 10 December 2021] (PT)
VC dimension and distribution-free sample-based testing
by Eric Blais, Renato Ferreira Pinto Jr., and Nathaniel Harms
See my comments.
[Merav at WIS's TOC seminar, 13 December 2021]
New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier
by Shimon Kogan and Merav Parter
See my comments.
[Seen on ECCC, 13 Januray 2022]
Approximating Large Powers of Stochastic Matrices in Small Space
by Gil Cohen, Dean Doron, and Ori Sberlo
See my comments.
[pointed out to me by Amir Abboud, 31 March 2022]
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng,
Maximilian Probst Gutenberg, and Sushant Sachdeva
See my comments.
[Seen on ECCC, 4 April 2022] (PRG)
Linear Hashing with $\ell_\infty$ guarantees
and two-sided Kakeya bounds by Manik Dhar and Zeev Dvir
See my comments.
[Seen on ECCC, 19 April 2022] (PT) (PPS)
Verifying The Unseen:
Interactive Proofs for Label-Invariant Distribution Properties
by Tal Herman and Guy Rothblum
See my comments.
[Theory Semianr at WIS, 23 May 2022] (PPS)
Proving as Fast as Computing:
Succinct Arguments with Constant Prover Overhead
by Noga Ron-Zewi and Ron Rothblum
See my comments.
[Found on ECCC, 19 June 2022] (PRG)
Hitting Sets Give Two-Sided Derandomization of Small Space
by Kuan Cheng and William Hoza
See my comments.
[David at WIS's Theory seminar, 11 July 2022] (RnC)
Fast and Simple Algorithms for All-Terminal Network Reliability
by David Karger
See my comments.
[Seri at WIS's Theory lunch, 13 July 2022] (RnC)
Hardness of Approximation in P via Short Cycle Removal:
Distance Oracles, Cycle Detection, and Beyond
by Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir
See my comments.
[Seen on ECCC, 14 July 2022] (RnC)
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes
from Semirandom CSP Refutation
by Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar
See my comments.
[Seen on ECCC, 16 July 2022] (RnC)
Almost Chor--Goldreich Sources and Adversarial Random Walks
by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman
See my comments.
[Seen on ECCC, 19 July 2022] (RnC)
On One-Sided Testing Affine Subspaces
by Nader Bshouty
See my comments.
[Alex at the TOC seminar of WIS, 15 August 2022] (PT)
Stability and testability of permutations' equations
by Alexander Lubotzky
See my comments.
[Seen on ECCC, 28 August 2022] (RnC)
Recent Progress on Derandomizing Space-Bounded Computation
by William Hoza
See my comments.
[Got reminded of it, 30 August 2022]
Reducing All-Pairs Shortest-Path to Matrix Multiplication
by Raimund Seidel (1992)
See my comments.
[Found on the web, 26 September 2022]
Lecture notes on Boolean Matrix Multiplication
by Virginia Vassilevska Williams
See my comments.
[Talk at the TheoryLunch at WIS, 19 October 2022] (RnC)
On (Near-)Optimal Algorithms for Sparse Convolution
by Nick Fischer
See my comments.
[Seen on ECCC, 17 November 2022]
Testing of Index-Invariant Properties in the Huge Object Model
by
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
See my comments.
[Seen on ECCC, 21 November 2022]
Random Walks on Rotating Expanders
by Gil Cohen and Gal Maor
See my comments.
[Max at the theory lunch of WIS, 4 January 2023]
Realizable Learning is All You Need
by Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
See my comments.
[TOC seminar at WIS, 30 January 2023] (RnC)
Algorithms Should Have Bullshit Detectors
(or Polynomial Time Byzantine Agreement with Optimal Resilience)
by Shang-En Huang, Seth Pettie and Leqi Zhu.
See my comments.
[Nathan at the theorylunch of WIS, 31 January 2023] (RnC)
Worst-Case to Expander-Case Reductions
by Amir Abboud and Nathan Wallheimer
See my comments.
[Thomas at a faculty lunch of WIS, 8 February 2023]
Proving inequality between objects
by proving that they cannot be approximated
by Thomas Vidick
See my comments.
[Greg at the TOC semimar of WIS, 13 March 2023]
Recent Progress on Fault Tolerant Spanners
by Greg Bodwin
See my comments.
[Seen on ECCC, 16 March 2023] (EXT)
Two Source Extractors for Asymptotically Optimal Entropy,
and (Many) More
by Xin Li
See my comments.
[Seen on ECCC, 26 April 2023] (PT)
A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions
on $d$-Dimensional Hypergrids
by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
See my comments.
[Seen on ECCC, 9 May 2023] (PT)
Linear Relaxed Locally Decodable and Correctable Codes
Do Not Need Adaptivity and Two-Sided Error
by Guy Goldberg
See my comments.
[Seen on ECCC, 25 May 2023] (RnC)
Polynomial-Time Pseudodeterministic Construction of Primes
by Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren,
and Rahul Santhanam
See my comments.
[Seen on ECCC, 27 May 2023] (PPS)
Batch Proofs are Statistically Hiding
by Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum,
and Prashant Nalini Vasudevan
See my comments.
[Private presentation by Omer, 1 June 2023] (PRG)
Outcome Indistinguishability
by Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, and Gal Yona
See my comments.
[Private presentation by Omer, 1 June 2023] (RnC)
Generative Models of Huge Objects
by Lunjia Hu, Inbal Livni-Navon, and Omer Reingold
See my comments.
[Seen on ECCC, 18 July 2023] (CT)
Depth-3 Circuits for Inner Product
by Mika Goos, Ziyi Guan, Tiberiu Mosnoi
See my comments.
[Seen on ECCC, 19 July 2023] (PRG)
On the Power of Regular and Permutation Branching Programs
by Chin Ho Lee, Edward Pyne, and Salil Vadhan
See my comments.
[Seen on ECCC, 25 July 2023] (PT)
Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries
by Gil Cohen and Tal Yankovitz
See my comments.
[Announced talk at MIT, 26 July 2023] (PT)
On Approximating Total Variation Distance
by A. Bhattacharyya, S. Gayen, K.S. Meel, D. Myrisiotis, A. Pavan,
and N.V. Vinodchandran.
See my comments.
[Henry in the algorithms seminar of WIS, 1 August 2023] (PT)
Spanning Adjacency Oracles in Sublinear Time
by Greg Bodwin and Henry Fleischmann
See my comments.
[Seen on ECCC, 8 August 2023] (CT)
Linear-Size Boolean Circuits for Multiselection
by Justin Holmgren and Ron Rothblum
See my comments.
[Pointed out by Amir Abboud, 9 August 2023] (CT)
Fredman's Trick Meets Dominance Product:
Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
by Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
See my comments.
[Pointed out by Amir Abboud, 15 August 2023] (CT)
Four works on fine-grained reductions
of approximate counting and uniform generation to decision
(*) Holger Dell and John Lapinskas.
Fine-grained reductions from approximate counting to decision.
(*) Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra.
Hyperedge Estimation using Polylogarithmic Subset Queries.
(*) Holger Dell, John Lapinskas, and Kitty Meeks.
Approximately counting and sampling
small witnesses using a colourful decision oracle.
(*) Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra.
Faster Counting and Sampling Algorithms Using Colorful Decision Oracle.
See my comments.
[Igor at the TOC seminar of WIS, 18 Sept 2023] (RnC)
Worst-Case to Average-Case Reductions via Additive Combinatorics
by Vahid Asadi, Sasha Golovnev, Tom Gur, Igor Shinkar
and Sathyawageeswar Subramanian
See my comments.
[Seen on ECCC, 29 Sept 2023] (PRG)
Counting Unpredictable Bits: A Simple PRG from One-way Functions
by Noam Mazor and Rafael Pass.
See my comments.
[Seen on ECCC, 1 Nov 2023] (RnC)
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
by Pravesh Kothari and Peter Manohar
See my comments.
[Seen on ECCC, 1 Nov 2023] (PT/PPS)
Doubly-Efficient Interactive Proofs for Distribution Properties
by Tal Herman and Guy Rothblum
See my comments.
[Seen in 64th FOCS, 8 Nov 2023] (RnC)
Work-Efficient Parallel Derandomization I:
Chernoff-like Concentrations via Pairwise Independence
by Mohsen Ghaffari, Christoph Grunau, and Vaclav Rozhon
See my comments.
[Seen in ECCC, 15 Nov 2023] (CT)
Tree Evaluation is in Space O(log n * log log n)
by James Cook and Ian Mertz
See my comments.
[Seen in ECCC, 19 Nov 2023] (CT)
The Non-Uniform Perebor Conjecture
for Time-Bounded Kolmogorov Complexity is False
by Noam Mazorand Rafael Pass
See my comments.
[Seen in ECCC, 16 Dec 2023] (CT)
New Graph Decompositions
and Combinatorial Boolean Matrix Multiplication Algorithms
by Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka
See my comments.
[Pointed out by Guy Rothblum, 20 Dec 2023] (PPS)
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
by Gal Arnon, Alessandro Chiesa, and Eylon Yogev.
See my comments.
[Got reminded, 25 Dec 2023] (PPS)
Constant-Round Arguments from One-Way Functions
by Noga Amit and Guy Rothblum
See my comments.
[Jad at the theory seminar of WIS, 27 Dec 2023] (RnC)
Explicit Codes for Poly-Size Circuits
and Functions that are Hard to Sample on Low Entropy Distributions
by Ronen Shaltiel and Jad Silbak
by
See my comments.
[Eliran at the TOC seminar of Weizmann, 5 Feb 2024]
Conflict Checkable and Decodable Codes and Their Applications
by Benny Applebaum and Eliran Kachlon
See my comments.
[Ronitt at the TOC seminar of Weizmann, 19 February 2024] (PT)
Properly learning monotone functions via local correction
by Jane Lange, Ronitt Rubinfeld and Arsen Vasilyan
See my comments.
[Seen on ECCC, 18-Aug-2023 (but waited for a revision till 1-Mar-2024)] (PT)
Distribution-Free Proofs of Proximity
by Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron Rothblum
See my comments.
[Algorithms meeting at Weizmann, 14-Mar-2024]
Faster Combinatorial Algorithms for Bipartite Matching
by Julia Chuzhoy and Sanjeev Khanna.
See my comments.
[Happened to see it (late), 21-Mar-2024] (PT)
Estimating the Effective Support Size in Constant Query Complexity
by Shyam Narayanan and Jakub Tetek
See my comments.
[Nathan at Weizmanan's theorylunch, 17-Apr-2024] (CT)
Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by Amir Abboud and Nathan Wallheimer
See my comments.
[found in a search, 28 April 2024] (RnC)
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
by Thatchaphol Saranurak and Di Wang
See my comments.
[Yotam at the WIS theory seminar, 6th May 2024] (CT)
New Derandomized Agreement Tests
by Yotam Dikstein, Irit Dinur, and Alex Lubotzky.
See my comments.
[Seen on PTreview,
12 May 2024.] (PT)
Testing Ck-freeness in bounded-arboricity graphs
by Talya Eden, Reut Levi, Dana Ron
See my comments.
[Seen in ECCC, 20 May 2024] (PT/PPS)
Interactive Proofs for General Distribution Properties
by Tal Herman and Guy Rothblum
See my comments.
[Seen in ECCC, 27 May 2024] (CT/CRY)
A Note on Zero-Knowledge for NP and One-Way Functions
by Yanyi Liu, Noam Mazor, and Rafael Pass.
See my comments.
[Seen in ECCC, 31 May 2024] (PRG)
Near-Optimal Averaging Samplers
by Zhiyang Xun and David Zuckerman
See my comments.
[MFO, 3-7 June 2024] (CT)
Some highlights of the Oberwolfach complexity workshop
A partial list includes
* Raghu Meka - Structure vs Randomness Redux: New Frontiers and Applications
* Amir Abboud - Recent Developments in Fine-Grained Complexity
* Avi Wigderson - Reading Turing’s Papers
* Pranjal Dutta - Recent Advances in Polynomial Identity Testing
* Venkatesan Guruswami - 3-query LCC
* Ron Rothblum - Batch Verification
* Pravesh Kothari -
Spectral Refutation for Semirandom CSPs and Applications to Local Codes
* Shuichi Hirahara - One-Way Functions and Zero Knowledge
* Venkatesan Guruswami - The Parameterized Inapproximability Hypothesis
* Shafi Goldwasser -- Verification of ML
* Xin Li - Recent Developments in the Theory of Randomness Extractors
See my comments.
[WIS's TOC seminar, 10 June 2024] (RnC)
Fast and Cheap Asynchronous Construction of Small $k$-Dominating Sets
by Yuval Emek
See my comments.
[BU, 10-11 July 2024] (CT)
Some highlights of the LevinFest
* Eric Allender -
The Minimum Circuit Size Problem through the Ages
* Levin's comment on Oded Goldreich's talk (Pseudorandom Generators)
* Igor Carboni Oliveira -
Levin Complexity and Pseudodeterministic Constructions of Primes
* Leonid Levin - Set Theory in the Foundation of Math:
Internal Classes, External Sets
* Madhu Sudan - Universality in Communication
See my comments.
[Pointed out by Dana, 5 August 2024] (PT)
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas
by Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
See my comments.
[Pointed out by Dana, 6 August 2024] (PT)
Testing versus estimation of graph properties, revisited
by Lior Gishboliner, Nick Kushnir, Asaf Shapira.
See my comments.
[Partially attended, 5-7 August 2024] (PT)
Workshop on Local Algorithms
(chaired by Clement Canonne)
See my comments.
[Seen on ECCC, 2 December 2024] (PT)
Settling the complexity of testing grainedness of distributions,
and application to uniformity testing in the Huge Object model
by Clement Canonne, Sayantan Sen, and Qiping Yang
See my comments.
[Seen on ECCC, 5 December 2024] (PT)
Testing vs Estimation
for Index-Invariant Properties in the Huge Object Model
by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi,
Gopinath Mishra, and Sayantan Sen
See my comments.
Go to the top of this page. Back to Oded Goldreich's homepage.