Colloquium Details
IBM Research/NYU/Columbia Theory Day
Speaker: Various Speakers
Location: Warren Weaver Hall 109
Date: November 11, 2011, 9:30 a.m.
Host: New York University
Synopsis:
Program
9:30 - 10:00 Coffee and bagels
10:00 - 10:55 Prof. Dana Ron On sublinear algorithms for approximating graph parameters
10:55 - 11:05 Short break
11:05 - 12:00 Dr. Mihai Patrascu Hashing for Linear Probing
12:00 - 2:00 Lunch break
2:00 - 2:55 Prof. Oded Regev Entropy-based Bounds on Dimension Reduction in L_1
2:55 - 3:15 Coffee break
3:15 - 4:10 Prof. Benny Pinkas Secure Computation on the Web: Computing without Simultaneous Interaction
For directions, please see http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu Tal Rabin talr@watson.ibm.com Baruch Schieber sbar@watson.ibm.com Rocco Servedio rocco@cs.columbia.edu
========= Abstracts =========
Prof. Dana Ron (Tel-Aviv University and Columbia University)
On sublinear algorithms for approximating graph parameters
When we refer to efficient algorithms, we usually mean polynomial-time algorithms. In particular this is true for graph algorithms, which are considered efficient if they run in time polynomial in the number of vertices and edges of the graph.
However, in some cases we may seek even more efficient algorithms whose running time is sublinear in the size of the input graph. Such algorithms do not even read the whole input graph, but rather sample random parts of the graph and compute approximations of various parameters of interest.
In this talk I will survey various such algorithms, where the parameters I will discuss are:
(1) The average degree the number of small stars (2) The weight of a minimum spanning tree (3) The size of a minimum vertex cover and a maximum matching (4) The number of edges that should be added/removed in order to obtain various properties
==================================================================
Dr. Mihai Patrascu (AT&T; Labs -- Research)
Hashing for Linear Probing
Hash tables are ubiquitous data structures solving the dictionary problem, and they often show up in inner loops, making performance critical.
A hash table algorithm relies crucially on a hash function, which quasirandomly maps a large domain (the input keys) to a small domain (the memory space available). Many "hash tables" (in effect, algorithms for dealing with collisions) have been proposed, the best known being collision chaining, linear probing and cuckoo hashing.
Among these, linear probing is ideally suited for modern computer architectures, which tend to favor linear scans. However, linear probing is quite sensitive to the quality of the hash function and, traditionally, good performance was only guaranteed by using highly independent (but slow) hash functions.
Our finding is that tabulation hashing, despite its low degree of independence, can actually guarantee very robust performance in linear probing. This function is both easy to implement and extremely fast on current hardware (faster than 2 multiplications), offering an ideal solution both in theory and in practice.
==================================================================
Prof. Oded Regev (Tel-Aviv University and CNRS, ENS, Paris)
Entropy-based Bounds on Dimension Reduction in L_1
We show that there exists an N-point subset of L_1 such that for every D>1, embedding it into \ell_1^d with distortion D requires dimension d at least N^{\Omega(1/D2)}, and that for every \eps>0 there exists an N-point subset of L_1 such that embedding it into \ell_1^d with distortion 1+\eps requires dimension d at least N^{1-O(1/\log(1/\eps))}. These results were previously proven by Brinkman and Charikar [JACM, 2005] and by Andoni, Charikar, Neiman, and Nguyen [FOCS 2011]. We provide an alternative and arguably more intuitive proof based on an entropy argument.
==================================================================
Prof. Benny Pinkas (Bar Ilan University and Google)
Secure Computation on the Web: Computing without Simultaneous Interaction
Secure computation enables mutually suspicious parties to compute a joint function of their private inputs while providing strong security guarantees. However, its use in practice seems limited. We argue that one of the reasons for this is that the model of computation on the web is not suited to the type of communication patterns needed for secure computation. Specifically, in most web scenarios clients independently connect to servers, interact with them and then leave. This rules out the use of secure computation protocols that require that all participants interact simultaneously.
We initiate a study of secure computation in a client-server model where each client connects to the server once and interacts with it, without any other client necessarily being connected at the same time. We point out some inherent limitations in this model and present definitions that capture what can be done. We also present a general feasibility result and several truly practical protocols for a number of functions of interest. All our protocols are based on standard assumptions, and we achieve security both in the semi-honest and malicious adversary models.
Joint work with Shai Halevi and Yehuda Lindell. ==================================================================
"Every Day is Theory Day"
Notes:
In-person attendance only available to those with active NYU ID cards.