New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, November 13, 2015
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.
External sponsorship by: Google

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.

Program:

Program

 9:30 - 10:00: Coffee and bagels

10:00 - 10:55: Prof. Mikkel Thorup
               Deterministic Edge Connectivity in Near-Linear Time

10:55 - 11:05: Short break

11:05 - 12:00: Prof. Daniel Wichs
               Homomorphic Cryptography beyond FHE

12:00 -  2:00: Lunch break

 2:00 -  2:55: Prof. Alexandr Andoni
               Sketching complexity of graph cuts

 2:55 -  3:15: Coffee break

 3:15 -  4:10: Dr. Noga Ron-Zewi
               High-rate locally-correctable and locally-testable
               codes with sub-polynomial query complexity



For directions, please see here and here (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
Rocco Servedio rocco@cs.columbia.edu



==================================================================

Abstracts

Deterministic Edge Connectivity in Near-Linear Time

Prof. Mikkel Thorup, University of Copenhagen

We present a deterministic algorithm that computes the
edge-connectivity of a graph in near-linear time. This is for a
simple undirected unweighted graph G with n vertices and m
edges. This is the first o(mn) time deterministic algorithm for
the problem. Our algorithm is easily extended to find a
concrete minimum edge-cut. In fact, we can construct the
classic cactus representation of all minimum cuts in
near-linear time.

The previous fastest deterministic algorithm by Gabow from
STOC'91 took ~O(m+k^2 n), where k is the edge connectivity, but
k could be Omega(n).

At STOC'96 Karger presented a randomized near linear time Monte
Carlo algorithm for the minimum cut problem. As he points out,
there is no better way of certifying the minimality of the
returned cut than to use Gabow's slower deterministic algorithm
and compare sizes.

Our main technical contribution is a near-linear time algorithm
that contract vertex sets of a simple input graph G with
minimum degree d, producing a multigraph with ~O(m/d) edges
which preserves all minimum cuts of G with at least 2 vertices
on each side.

In our deterministic near-linear time algorithm, we will
decompose the problem via low-conductance cuts found using
PageRank a la Brin and Page (1998), as analyzed by Andersson,
Chung, and Lang at FOCS'06. Normally such algorithms for
low-conductance cuts are randomized Monte Carlo algorithms,
because they rely on guessing a good start vertex. However, in
our case, we have so much structure that no guessing is needed.

Joint work with Ken-ichi Kawarabayashi.

==================================================================

Homomorphic Cryptography beyond FHE

Prof. Daniel Wichs, Northeastern University
                        
This talk will explore recent schemes that enable homomorphic
computation over cryptographic data, beyond (only) fully
homomorphic encryption (FHE). We will start with the
beautifully simple FHE scheme due to Gentry, Sahai and Waters
(CRYPTO '13). We will then show how to use the versatile
structure of this scheme to construct other powerful primitives
such as fully homomorphic signatures and multi-key FHE.

================================================================== 

Sketching complexity of graph cuts

Prof. Aleksandr Andoni, Columbia University

We study the problem of sketching an input graph so that, given
the sketch, one can estimate the value (capacity) of any cut in
the graph up to a small approximation, 1+epsilon. The classic
construction of [Benczur, Karger 1996] implies a sketch of size
essentially proportional to the number of vertices and the
*square* of 1/epsilon.

We show that the dependence on epsilon can be brought down to
only linear in 1/epsilon, if one tolerates a slightly weaker
guarantee. Namely, we give a randomized scheme which, given
accuracy epsilon and an n-vertex graph G=(V,E), produces a
sketch of size O~(n/epsilon), from which one can report the
capacity of any fixed cut within approximation factor
(1+epsilon) with high probability. This "for each" guarantee
remains useful in certain applications.

To complement the above, we also show that the weaker guarantee
is unavoidable for the improved dependence on epsilon. In
particular, if a sketch succeeds in estimating the capacity of
*all* cuts in the graph simultaneously, it must have size at
least Omega(n/epsilon^2) bits.

Joint work with Jiecao Chen, Robert Krauthgamer, Bo Qin, David
P. Woodruff, Qin Zhang.

================================================================== 

High-rate locally-correctable and locally-testable
codes with sub-polynomial query complexity

Dr. Noga Ron-Zewi, Institute for Advanced Study

Locally-correctable codes (LCCs) and locally-testable codes
(LTCs) are special families of error-correcting codes that
admit highly efficient sub-linear time algorithms for error
correction and detection, respectively, while making a small
number of queries to the received word.

LCCs and LTCs were originally studied in complexity theory
because of their close relationship to program checking and
probabilistically-checkable proofs (PCPs), but in recent years
there has been a new incentive for their study due to their
potential use for massive data transmission and storage
purposes and the successful implementation of related families
of local codes in cloud storage systems.

We show constructions of LCCs and LTCs with constant rate,
constant relative distance, and sub-polynomial number of
queries and running time of the form $exp(sqrt{log n})$ for
length n codewords. Prior to our work, such codes were known to
exist only with polynomial number of queries and running time
of the form $n^{beta}$ (for a constant $beta>0$). and there
were several, quite different, constructions known.

Along the way, we also construct LCCs and LTCs over large (but
constant) size alphabets, with the same number of queries and
running time of $exp(sqrt{log n})$, which additionally have the
property of approaching the Singleton bound: they have almost
the best-possible relationship between their rate and distance.
Such a result was previously not known for any sub-linear
number of queries and running time.

If time permits I will also discuss a more recent work that
further improves the running time and number of queries of LTCs
to a quasi-polylogarithmic function of the form $(log n)^{O(log
log n)}$.

Joint work with Swastik Kopparty, Or Meir and Shubhangi Saraf

==================================================================