Haifa U. CS Theory Seminar - 2003-04
Oct. 30 - Ilan Newman (Haifa U), A survey on Property testing.
Nov. 13 - Sefi
Naor (Technion), abstract: The Online Set Cover Problem
Nov. 20 - Uri Rabinovich (Haifa U.) - On the theory of Finite Metric spaces.
Nov. 27 - Ilan Newman (Haifa U.),
abstract: Computing in fault tolerance broadcast networks
Dec. 4 -
Uri Zwick (Tell-Aviv U.),
abstract: Finding short directed cycles using rectangular
matrix multiplication and dynamic programming
Dec. 11 - Sofya Raskhodnikova (Hebrew
abstract: Lower bound for testing properties representable by 3-cnf
Dec. 18 -
Uri Feige (Weizmann Inst.),
abstract: Algorithms for semirandom instances of
Dec 25 -
Eli Ben-Sasson, Harvard U. ,
abstract: Shorter PCPs and Applications to Coding
Jan 1 - Avner Magen (Toronto U.),
abstract: Sublinear Geometric Algorithms
Jan 15 - Shlomo Hoory, Toronto U.
abstract: Rank Bounds and Integrality Gaps for Geometric Proof Systems.
March 4 - Amir Ronen, Technion,
abstract: On the Expected Payment of Mechanisms for Task Allocation
March 11 - Ronen Shaltiel, TBA
March 15 - Amnon Ta-Shama (TAU), TBA
April 15 - Nati Linial (Hebrew U), abstract:
April 22 - Noga Alon (Tell-Aviv U), abstract:
April 29 - Noam Nisan (Hebrew U), abstract:
May 6 - Asaf Shapira (Tell-Aviv U.) , abstract:
May 13 - Funda Ergun (Simon Fraser University), abstract:
May 27, June 3 - No seminar - workshop on metric spaces.
June 10 - Danny Keren (Haifa U),
On antifaces in Image Processing.
June 17 - Ron Lavi (HUJI), abstract:
Academic year 2005
Oct. 28 - Oded Lachish, Haifa U. - abstract: Periodicity Testing
Nov. 4, 12:00 - Benny Pinkas, HP. - abstarct:
Keyword Search and Oblivious Pseudorandom
Nov. 11 - Ronen Shaltiel, Haifa U. TBA.
Nov. 18 - Oded Regev, Tell-Aviv U. - abstract: Lattice-based Cryptography, Quantum, Learning, and Decoding Random
Nov. 25 - Amir Shpilka, Weizmann Inst. abstract: Locally Decodable Codes with 2 Queries and Polynomial Identity
Testing for Depth 3 Circuits.
Dec. 2 - Moshe Tennenholtz, Technion, abstract: Beyond Mechanism Design: Competitive Safety Analysis and K-Implementation
Dec. 9 - Howard Karloff, ATT Research, abstract: How Well Can the *Directed* Traveling Salesman Problem Be Approximated?
Dec. 16 - Igor Pak, MIT (visiting Hebrew University) abstract: What do combinatorialists do?
Dec. 23 - Yuval Ishai, Technion, abstract: Cryptography in NC0
Dec. 30 - Robi Krauthgammer, abstract:
A Metric Notion of Dimension and its Algorithmic Applications
Jan 13 - Shlomo Hoory, Toronto U, abstract:
Simple permutations mix well
Mar. 1, 12:00, - Manor Mendel, California Institute of Technology, abstract: Algorithmic Aspects of Finite
Metric Spaces. Note the special day -
talk will take place at Jacobs Bld. room 303.
Mar. 10 - Adam Smith, Weizmann Inst. abstract: Correcting Errors Without
Leaking Partial Information.
Mar. 17 - Danny Gutfreund, Hebrew UNiversity, abstract: If NP languages are hard in the worst-case then it is easy to find
their hard instances.
Mar. 24 - Eldar Fischer, Technion, abstract: Property testing and tolerance.
Mar. 31 - Alex Samorodnitsky, Henrew University, abstract:
Linear programming bounds for ball packing
Apr. 7 - Omer Reingold, Weizmann Inst. - undirected connectivity
on deterministic LOG space.
Apr. 14 - Yossi Azar, Tell Aviv U., abstract: The Price of Routing Unsplittable Flow
May. 19 - Cancelled - there is a workshop May 16-19, 2005, at
CRI titled Fifth Annual Workshop on Interdisciplinary Applications of
Graph Theory, Combinatorics and Algorithms, including a talk
of Krishna Palem at the time of
the theory seminar.
More information at .
May. 26 - Moni Naor, Weizmann Institute, TBA.
June 2 - No activity - student day.
June 9 - Arie Matsliah, Technion, Testing graph isomorphism
Nov. 10 - Ronen Shaltiel, Haifa U., abstract: Simulating Independence: New Constructions of Condensers, Ramsey
Graphs, Dispersers, and Extractors
Nov. 17 - Yuval Rabani, Technion, abstract: Low Distortion Embeddings for Edit Distance.
Nov. 24 - Nati Linial, Hebrew University, abstract: Complexity measures for sign matrices.
Dec. 1 - Irit Dinur, Hebrew University, abstract: The PCP Theorem by gap amplification.
Dec. 8 - Michael Elkin, abstract: Lower-Stretch Spanning Trees
Dec. 15 - Robi Krauthgamer, abstract: Unstructured data: practical algorithms with rigorous analysis.
Dec. 22 - Shakhar Smorodinsky, abstract: Conflict-Free Colorings.
Dec. 29 - Manor Mendel, TBA
Jan 5 - , Ofer Neiman, abstract: Metric Embedding with Relaxed Guarantees
Jan 12 - Liam Roditty, abstract: Developments in Dynamic Graph Algorithms.
Jan 19 - Moshe Schwartz, TBA
Jan 26 - Adi Akavia, abstract: On the (Im)Possibility of Basing One-Way Functions on NP-Hardness.
Mar 9 - Rob Van Stee, abstract: Speed scaling with precedence constraints
Mar 16 - Amir Shpilka, abstract: New
constructions of epsilon-biased generators.
Mar 16 - Eli Berger, abstract: Proof of Berge's Strong Path Partition Conjecture for k=2
Mar 30 - Alex Samorodnitsky, TBA
Apr 6 - Faith Fich, abstract: Time-Space Tradeoffs for Implementations of Snapshots
Apr 27 - Shmuel Onn, abstract: Convex Integer Optimization and Universality of Multiway Polytopes
May 4 - Amir Ronen, abstract: Prediction Games
May 11 - Uri Rabinovich, abstract: Embedding graph metrics in Euclidean space and the spectral
pproperties of Cayley graphs.
May 18 - Yishay Mansour, abstract: The Communication Complexity of Uncoupled Nash Equilibrium Procedures.
May 25 - No lecture - student day.
June 8 - Michael Krivelevich, Testing triangle freeness in general graphs.
June 15 - no talk
June 22 - Danny Harnik, abstract: On the power of the randomized iterate