Weizmann Institute of Science

Faculty of Mathematics and Computer Science

Foundations of Computer Science Seminar

(Former title: Cryptography and Complexity Seminar)

Record of past seminars (since 1/1/01)

Last updated: August 2005.

Upcoming Seminars

See the seminar's webpage.

Related Material: the Theory of Computation at WIS webpage.

Past Seminars (from 1/1/01 till Aug'05)

(Titles up to Feb. 11, 2001 were reconstructed from memory.)

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.

Record of talks in the academic year 2003-04 is not available from this page...

This page is maintained by Oded Goldreich.