Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, June 22, 2004, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Moshe Lewenstein (Bar Ilan Univ.)

Peeling Codes with Applications to Finding Witnesses

We consider the general setting in which there is a set S, with elements taken from some commutative group G, of which we seek to discover k elements. The set S is not provided to us explicitly. Rather, we are provided procedures such that for any set A, we can compute the size of S ∩ A and the sum (in the group) of the elements in this intersection. We are interested in minimizing the total work to discover the k elements. We introduce the notion of Peeling Collections (or Peeling Codes) which provide efficient solutions to several versions of this general setting. We then show that the solution to this general problem provides improved algorithms for several known and new problems. These include: the k-witnesses (mismatches), the k-aligned ones, and the half-rectangular matching problems; the k-witnesses for boolean matrix multiplication, and the all pairs k-shortest paths problems; and the counterfeit coin finding problem.

(Joint work with Yonatan Aumann, Noa Lewenstein and Dekel Tsur)

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login