Haifa U. CS Theory Seminar - 2003-04


2003

  • 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 U.), abstract: Lower bound for testing properties representable by 3-cnf formulas.

  • Dec. 18 - Uri Feige (Weizmann Inst.), abstract: Algorithms for semirandom instances of NP-hard problems

  • Dec 25 - Eli Ben-Sasson, Harvard U. , abstract: Shorter PCPs and Applications to Coding Theory.

    2004

  • 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 Functions.

  • Nov. 11 - Ronen Shaltiel, Haifa U. TBA.

  • Nov. 18 - Oded Regev, Tell-Aviv U. - abstract: Lattice-based Cryptography, Quantum, Learning, and Decoding Random Linear Codes

  • 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. sets.

  • June 2 - No activity - student day.

  • June 9 - Arie Matsliah, Technion, Testing graph isomorphism sets.

    2006

  • 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