**Related Material:**
the Theory of Computation at WIS webpage.

**January 7, 2001:**
Robert Krauthgamer (Weizmann).
A polylogarithmic approximation of the minimum bisection.

**January 14, 2001:**
Boaz Barak (Weizmann).
On the (Im)possibility of Obfuscators.

**January 21, 2001:**
Michael Krivelevich (Tel-Aviv University).
The Regularity Lemma and its appplications to Property Testing.

**January 28, 2001:**
Gil Kalai (Hebrew University).
Fourier Transform of Boolean Functions.

**February 4, 2001:**
Alon Rosen (Weizmann).
An almost loagrithmic lower-bound on the number of rounds
in concurrent zero-knowledge.

**February 11, 2001:**
Michael Elkin (Weizmann). Relaxed notions of graph spanners.

**February 25, 2001:**
Itsik Mantin (Weizmann). *The security of RC4.*

**March 4, 2001:**
Amnon Ta-Shma (Tel-Aviv University).
*Extractors from Reed-Muller Codes.*

**March 25, 2001:**
Yael Tauman (Weizmann).
*Improved On-line/Off-line Signature Schemes*.

**April 29, 2001:**
Alon Rosen (Weizmann).
*Generating Random Factored Numbers, Easily (by Adam Kalai)*

**June 17, 2001:**
Eric Vigoda (Weizmann).
*Approximating the permanent*.

**June 24, 2001:**
Eric Vigoda (Weizmann).
*Approximating the permanent (cont'ed: proof of key lemma)*.

**July 1, 2001:**
Erez Petrank (Technion).
*Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds*.

**July 15, 2001:**
Ziv Bar-Yossef (UC-Berkeley).
*Sampling Algorithms: Lower Bounds and Applications*.

**October 28, 2001:**
Ronen Shaltiel (Weizmann).
*Explicit constructions of pseudo-random generators and extractors*.

**November 4, 2001:**
Ronen Shaltiel (Weizmann).
*Simple extractors for all min-entropies
and a new pseudo-random generator*.

**November 11, 2001:**
Oded Goldreich (Weizmann).
On Interactive Proofs with Laconic Provers.

**November 18, 2001:**
Nati Linial (Hebrew University).
*Girth and Euclidean Distortion*.

**November 25, 2001:**
Adi Shamir (Weizmann).
*How to Leak a Secret*.

**December 9, 2001:**
Oded Goldreich (Weizmann).
Three Theorems regarding Testing Graph Properties.

**December 16, 2001:**
Amos Beimel (Ben-Gurion University),
*On Linear and Nonlinear Secret-Sharing*

**December 23, 2001:**
Adam Kalai (MIT),
*Follow the leader for online algorithms*.

**December 30, 2001:**
Alex Samorodnitsky (Hebrew University),
*Testing monotonicity on general posets*.

**January 6, 2002:**
Dana Ron (Tel-Aviv University),
*Proclaiming Dictators and Juntas or Testing Boolean Formulae*.

**February 3, 2002:**
Omer Reingold (ATT).
*Randomness Conductors and Constant-Degree Expansion Beyond
the Degree/2 Barrier*.

**February 10, 2002:**
Boaz Barak (Weizmann).
*How To Go Beyond the Black-Box Simulation Barrier*.

**February 17, 2002:**
Nir Piterman (Weizmann).
*From Bidirectionality to Alternation* (in finite automata).

**March 3, 2002:**
Moni Naor (Weizmann).
*Anti-persistence: History Independent Data Structures*.

**March 10, 2002:**
Avi Wigderson (IAS and HU).
*Expander graphs - where Combinatorics and Albegra compete and cooperate*.

**March 17, 2002:**
Madhu Sudan (MIT).
*List decoding of error-correcting codes*.

**March 24, 2002:**
Irit Dinur (Institute for Advanced Study).
*Hardness of Hyper-Graph Coloring*.

**April 14, 2002:**
Uri Zwick (TAU).
*Approximate Distance Oracles*.

**May 5, 2002:**
Amir Shpilka (Weizmann).
*Lower bounds for matrix product, in bounded depth circuits
with arbitrary gates*.

**May 26, 2002:**
Eric Winfree. *Designing in-vitro biomolecular algorithms with DNA:
self-assembly and transcriptional networks*.

**June 2, 2002:**
Eli Ben-Sasson (Harvard University).
*Lower Bounds for Bounded Depth Frege Proofs via Buss-Pudlak Games*.

**June 9, 2002:**
David Harel (Weizmann).
*On the Behavior of Complex Reactive Systems*.

**June 16, 2002:**
Amir Shpilka (Weizmann).
*Affine projections of symmetric polynomials*.

**June 18, 2002:**
Eyal Kushilevitz (Technion).
*Breaking the $O(n^{1/(2k-1)})$ Barrier for
Information-Theoretic Private Information Retrieval*.

**June 23, 2002:**
Moni Naor (Weizmann).
*Revocation and Tracing Schemes for Stateless Receivers*.

**June 30, 2002:**
Alexander Klimov and Anton Mityagin (Weizmann).
*Analysis of Neural Cryptography*.

**July 7, 2002:**
Michael Elkin (Weizmann).
*Computing Almost Shortest Paths*.

**July 21, 2002:** Elhanan Mosel. *Learning Juntas*

**July 28, 2002:** Yehuda Lindell (Weizmann). A farewell lecture:
*Strict Polynomial-time in Simulation and Extraction*.

**October 13, 2002:** Jens Groth (BRICS).
*A Verifiable Secret Shuffle of El-Gamal Ciphertexts*.

**October 20, 2002:** Alon Rosen (WIS).
*Concurrent Zero-Knowledge with Logarithmic Round Complexity*.

**October 22, 2002:** Michael Langberg (WIS).
*Graphs with tiny vector chromatic numbers and huge chromatic numbers*.

**November 24, 2002:** Shakhar Smorodinsky (TAU).
*On Conflict-Free Coloring of Points*.

**December 15, 2002:** Robi Krauthgamer (UC-Berkeley).
*Polylogarithmic Inapproximability*.

**December 17, 2002:** Eric Vigoda (U. of Chicago).
*Non-Markovian Coupling*.

**December 22, 2002:** Kobbi Nissim (DIMACS and NECI).
*Efficient Oblivious Computation*.

**December 24, 2002:** Tal Malkin (ATT and Columbia U.).
*Efficient Generic Forward-Secure Signatures With An Unbounded Number
Of Time Periods*

**January 5, 2003:** Asaf Shapira (TAU).
*Testing Subgraphs in Directed Graphs*

**February 2, 2003:** Anton Mityagin.
*Query Complexity of Finding a Local Maximum Point*

**February 9, 2003:** Dekel Tsur (TAU).
*Improved Algorithms for the Random Cluster Graph Model*

**February 16, 2003:** Yaron Sella (HU).
*On The Computation-Storage Trade-offs of Hash Chain Traversal*

**February 18, 2003:** Oded Goldreich (WIS).
Locally Testable Codes
and PCPs of Almost-Linear Length.

**March 2, 2003:**Ronen Shaltiel (WIS).
*Uniform hardness versus randomness tradeoffs for Arthur-Merlin games*.

**March 9, 2003:**Michael Elkin (IAS).
*Inapproximability and Every-Case Complexity of the
Distributed Minimum Spanning Tree Problem*.

**March 11, 2003:**Muli Safra (TAU).
*Analysis of Boolean Functions and (a small sample of) its Applications*.

**March 30, 2003:** Eran Tromer (WIS).
*Hardware-Based Parallelization of Factoring Algorithms*.

**April 6, 2003:** Moni Naor (WIS).
*Fighting spam may be easier than you think*.

**May 4, 2003:** Noam Kogan (TA Univ). *A Practical
Revocation Scheme for Broadcast Encryption Using Smart Cards*.

**May 11, 2003:** Scott Aaronson (UC-Berkeley).
*Quantum Lower Bound for the Collision Problem*.

**May 18, 2003:** Tali Kaufman (TAU).
*Testing Bipartitness in General Graphs*.

**June 1, 2003:** Boaz Barak (WIS).
*Constant-Round Coin-Tossing With a Man in the Middle
or Realizing the Shared Random String Model*.

**June 8, 2003:** Tzvika Hartman (WIS). *A Simpler 1.5-Approximation
Algorithm for Sorting by Transpositions*.

**June 15, 2003:** Yael Tauman (WIS).
*The (In)security of the Fiat-Shamir Paradigm*.

**June 22, 2003:** Adi Akavia (WIS). *A unifying approach
for proving hard-core predicates using list decoding*.

**June 29, 2003:** Danny Harnik (WIS).
*Completeness in Two-Party Secure Computation Revisited*.

**July 6, 2003:** Udi Wieder (WIS).
*Scalable and Dynamic Quorum Systems*.

Note the gap: Record of talks in the academic year 2003-04 is not available here.

**October 24, 2004:**
Yuval Ishai (Technion).
*Cryptography in NC0.*

**October 31, 2004:** Oded Regev (TAU).
*Lattice based cryptography, quantum and some learning theory.*

**November 7, 2004:** Gabriel Nivasch (WIS).
*On the Sprague--Grundy function for Wythoff's game.*

**November 14, 2004:** Uri Zwick (TAU).
*Deterministic construction of approximate distances oracles and spanners.*

**November 21, 2004:** Yehuda Lindell (Bar-Ilan).
*Concurrent General Composition of Secure Protocols in the Timing Model.*

**November 28, 2004:** Eyal Rozenman (WIS).
*A New Explicit Construction of Constant-Degree Expander Cayley Graphs*.

**November 29, 2004 (14:30 in Room 1):** Abhi Shelat (MIT).
*Collusion-Free Protocols*.

**December 5, 2004:** Asaf Shapira (TAU).
*Extremal Graphs, Recursive Functions
and a Separation Theorem in Property Testing*.

**December 12, 2004:** Nir Ailon (Princeton).
*Aggregating Inconsistent Information: Ranking and Clustering*.

**December 13, 2004 (14:30 in Room 1):** Omer Reingold (WIS).
*Undirected ST-Connectivity in Log-Space (SL=L)*.

**December 19, 2004** Yael Tauman Kalai (MIT).
*Smooth Projective Hashing and Two-Message Oblivious Transfer*.

**December 27, 2004 (14:30 in Room 1):** Adam Smith (WIS)
*Toward Privacy in Public Databases.*

**January 2, 2005:** Zvi Lotker (CWI)
*How far is randomness from order*.

**January 9, 2005:** Zeev Dvir (WIS).
*Locally Decodable Codes with 2 Queries
and Polynomial Identity Testing for Depth 3 Circuits*.

**March 20, 2005:** Danny Harnik (WIS),
*On robust combiners for oblivious transfer and other primitives*.

**March 27, 2005:** Boaz Tsaban (Bar-Ilan and WIS),
*Fast forward permutations and permutation graphs*.

**April 3, 2005:** Uri Nadav (WIS),
*Fault-Tolerant Storage and Quorum systems for dynamic environments*.

**April 10, 2005:** Ronen Shaltiel (Haifa U.),
*Pseudorandomness for approximate counting and sampling*.

**April 17, 2005:** Danny Hendler (U. of Toronto),
*A tight time bound for distributed counting and related problems*.

**May 8, 2005:** Adam Smith (WIS),
*Correcting errors without leaking partial information*.

**May 15, 2005:** Ariel Gabizon (WIS), *Deterministic extractors
for bit-fixing sources by obtaining an independent seed*.

**May 22, 2005:** Dan Boneh (Stanford),
*Chosen ciphertext security from bilinear maps*.

**May 29, 2005:** Irit Dinur (HU),
*The PCP Theorem by gap amplification*.

**June 20, 2005:** Julia Chuzoy (MIT),
*New thresholds of approximability: problems and techniques*.

**June 26, 2005:** Tali Kaufman (TAU),
*Sparse linear codes are locally testable*.

**July 3, 2005:**
Ronen Shaltiel (Hafia U.).
*Simulating independence: new constructions of condensers,
Ramsey graphs, dispersers, and extractors.*

**July 17, 2005:** Boaz Barak (Princeton).
*How to play almost any mental game over the net -
Concurrent compostition via super-polynomial simulation.*

**July 24, 2005:** Uri Feige (WIS).
*Algorithms for finding small vertex separators in graphs.*

**August 7, 2005:** Eyal Rozenman (WIS),
*Derandomized squaring of graphs
and a new algorithm for undirected ST connectivity*.

**August 14, 2005:** Ariel Gabizon (WIS).
*Deterministic extractors for affine sources over large fields*.

This page is maintained by Oded Goldreich.