תכנית מרכזי המצוינות

אירועים

# מרכז המצוינות באלגוריתמים ערך כנס

מרכז המצוינות באלגוריתמים ערך כנס בתאריך ה-27 בינואר 2012.

לחץ כאן על מנת לצפות בוידאו הכנס.

ראה למטה לו"ז הכנס והתקצירים.

The following is the schedule:
9:30 - 10:00 gathering and refreshments.
10:00 - 10:45 Adi Shamir (Weizmann), What is the Simplest Possible Provably Secure Block Cipher?
10:45 - 11:30 Iftach Haitner (TAU),  Coin Flipping with Constant Bias Implies One-Way Functions
11:30 - 11:45 Break
11:45 - 12:30 Yuval Rabani (HUJI), A constant factor approximation algorithm for reordering buffer management
12:30 - 13:15 Seffi Naor (Technion), A Polylogarithmic-Competitive Algorithm for the k-Server Problem

--------------------------------------------------------------------------------------------------------------

### Abstracts:

What is the Simplest Possible Provably Secure Block Cipher?
department of computer science & applied mathematics.
Weizmann institute of science

In 1991, Even and Mansour tried to answer this question by developing a new type of block cipher which uses a single publicly known random permutation as its core component. However, the exact security of their scheme remained unknown, since the best known lower bound proof uses known messages, whereas the best known upper bound attack requires chosen messages. In this talk I will present the Even-Mansour scheme, describe the new SLIDEX attack on it which finally solves this long standing open problem, and introduce the single key variant of the Even Mansour scheme which is arguably the simplest possible block cipher which has a tight bound on its security. The talk will be self contained, requiring no prior knowledge in cryptography.
Joint work with Orr Dunkelman and Nathan Keller.

Coin Flipping with Constant Bias Implies One-Way Functions
Iftach Haitner
School of Computer Science.
Tel Aviv University

It is well known (c.f., Impagliazzo and Luby [FOCS '89]) that the existence of almost all interesting" cryptographic applications, i,e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. While Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known.
We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, \frac{\sqrt2 -1}2 - o(1)) imply one-way functions.
Joint work with Eran Omri

A constant factor approximation algorithm for reordering buffer management
Yuval Rabani
School of Computer Science
The Hebrew University of Jerusalem

In the reordering buffer management problem (RBM) a sequence of $n$ colored items enters a buffer with limited capacity $k$. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total number of color changes in the output sequence. The problem formalizes numerous applications in computer and production systems, and is known to be NP-hard.
We give the first constant factor approximation guarantee for RBM. Our algorithm is based on an intricate rounding" of the solution to an LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of $O(\sqrt{\log k})$ of Adamaszek et al. (STOC 2011) that used different methods and gave an online algorithm. Our constant factor approximation beats the super-constant lower bounds on the competitive ratio given by Adamaszek et al. This is the first demonstration of an offline algorithm for RBM that is provably better than any online algorithm.
Joint work with Noa Avigdor-Elgrabli

A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Seffi Naor
Computer Science Dept.
Technion

The k-server problem is one of the most fundamental and extensively studied problems in online computation. Suppose there is an n-point metric space and k servers are located at some of the points of the metric space. At each time step, an online algorithm is given a request at one of the points of the metric space, and this request is served by moving a server to the requested point (if there is no server there already). The cost of serving a request is defined to be the distance traveled by the server. Given a sequence of requests, the task is to devise an online strategy minimizing the sum of the costs of serving the requests. The problem has a long history and the best deterministic algorithm known is (2k-1)-competitive (Koutsoupias and Papadimitriou, 1994).
We give the first polylogarithmic-competitive randomized online algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of $O(\log^3 n \log^2 k)$ for any metric space on $n$ points.
This is joint work with Nikhil Bansal, Niv Buchbinder, and Aleksander Madry and it appeared in FOCS 2011.