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 semiannual 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 45) hourlong
presentations by leading theoretical computer scientists about
stateoftheart 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 NearLinear 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 RonZewi
Highrate locallycorrectable and locallytestable
codes with subpolynomial 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/theoryny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
Tal Rabin talr@watson.ibm.com
Rocco Servedio rocco@cs.columbia.edu
==================================================================
Abstracts
Deterministic Edge Connectivity in NearLinear Time
Prof. Mikkel Thorup, University of Copenhagen
We present a deterministic algorithm that computes the
edgeconnectivity of a graph in nearlinear 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 edgecut. In fact, we can construct the
classic cactus representation of all minimum cuts in
nearlinear 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 nearlinear 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 nearlinear time algorithm, we will
decompose the problem via lowconductance cuts found using
PageRank a la Brin and Page (1998), as analyzed by Andersson,
Chung, and Lang at FOCS'06. Normally such algorithms for
lowconductance 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 Kenichi 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 multikey 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 nvertex 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.
==================================================================
Highrate locallycorrectable and locallytestable
codes with subpolynomial query complexity
Dr. Noga RonZewi, Institute for Advanced Study
Locallycorrectable codes (LCCs) and locallytestable codes
(LTCs) are special families of errorcorrecting codes that
admit highly efficient sublinear 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
probabilisticallycheckable 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 subpolynomial 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 bestpossible relationship between their rate and distance.
Such a result was previously not known for any sublinear
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 quasipolylogarithmic function of the form $(log n)^{O(log
log n)}$.
Joint work with Swastik Kopparty, Or Meir and Shubhangi Saraf
==================================================================
