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.