Columbia University Department of Computer Science



New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, November 11, 2011
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York Metropolitan area for one day of interaction and discussion.  The Theory Day features several (usually 4-5) hour-long presentations by leading theoretical computer scientists about state-of-the-art advances in various areas.  Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.



 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 Pătraşcu

		 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 here and here (building 46)

To subscribe to our mailing list, follow instructions at


Yevgeniy Dodis

Tal Rabin

Baruch Schieber

Rocco Servedio



                          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 Pătraşcu

                    (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/D^2)}, 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.