Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Warren Weaver Hall 109
Date: November 13, 2015, 9:30 a.m.
Host: Courant Institute of Mathematical Sciences, New York University
Synopsis:
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 meeting is free and open to everyone; in particular, students are encouraged to attend.
Program
9:30 - 10:00 Coffee and bagels
10:00 - 10:55 Prof. Mikkel Thorup (University of Copenhagen) Deterministic Edge Connectivity in Near-Linear Time
10:55 - 11:05 Short break
11:05 - 12:00 Prof. Daniel Wichs (Northeastern University) Homomorphic Cryptography beyond FHE
12:00 - 2:00 Lunch break (lunch not provided)
2:00 - 2:55 Prof. Alexandr Andoni (Columbia University) Sketching complexity of graph cuts
2:55 - 3:15 Coffee break
3:15 - 4:10 Dr. Noga Ron-Zewi (Institute for Advanced Study, Rutgers University) High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
For directions, please see http://www.cims.nyu.edu/direct.html and http://www.nyu.edu/content/dam/nyu/advertisePublications/documents/nyu-downloadable-campus-map.pdf (building 77)
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
=======================================================================
Prof. Mikkel Thorup (University of Copenhagen)
Deterministic Edge Connectivity in Near-Linear Time
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.
-------------------------------------------------------------------------
Prof. Daniel Wichs (Northeastern University)
Homomorphic Cryptography beyond FHE
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.
-------------------------------------------------------------------------
Prof. Aleksandr Andoni (Columbia University)
Sketching complexity of graph cuts
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.
-------------------------------------------------------------------------
Dr. Noga Ron-Zewi (Institute for Advanced Study, Rutgers University)
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
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
Notes:
In-person attendance only available to those with active NYU ID cards.