Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Mudd Building, Columbia University CSB 451
Date: May 10, 2019, 9:30 a.m.
Host: Columbia University, New York
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.
The Theory Day will be held on Columbia University campus, in CSB 451, Mudd building (a brand new CS auditorium!). For directions, please see here.
Some travel support is provided by DIMACS/Simons Collaboration in Lower Bounds in Computational Complexity through NSF grant #CCF-1836666.
To subscribe to our mailing list, follow the instructions here.
Organizers:
Program
| 9:30 - 10:00 | Coffee and bagels |
| 10:00 - 10:55 |
Dr. Tal Rabin (Algorand Foundation) |
| 10:55 - 11:05 | Short break |
| 11:05 - 12:00 |
Dr. Sepehr Assadi (Princeton University) |
| 12:00 - 2:00 | Lunch Break |
| 2:00 - 2:55 |
Prof. Mark Zhandry (Princeton University) |
| 2:55 - 3:15 | Coffee break |
| 3:15 - 4:10 |
Prof. Omri Weinstein (Columbia University) |
| 4:30 - 5:30 | Follow-up social |
Speakers
Dr. Tal Rabin (Algorand Foundation)
Advancing theory towards practice--the story of threshold cryptography
NIST (National Institute of Standards and Technology) has initiated an effort to standardize Threshold Cryptography. In this talk we will explain the notion of threshold cryptography, its uses and a proposal for the standard.
Based on work with Christian Cachin, Hugo Krawczyk, Jason Resch and Chrysoula Stathakopoulou.
Dr. Sepehr Assadi (Princeton University)
Sublinear Algorithms for (Delta+1) Vertex Coloring
In this talk, we will examine a classical graph coloring problem through the lens of sublinear algorithms these are algorithms that use computational resources that are substantially smaller than the size of the input on which they operate. It is well-known that any graph with maximum degree Delta admits a proper vertex coloring with (Delta + 1) colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one Find such a coloring via a sublinear algorithm? We will present results that answer this question in the affirmative for several well-studied models of sublinear computation, most notably, graph streaming and sublinear time algorithms. We obtain these results by proving a palette sparsification theorem which says that if every vertex independently samples O(log n) colors from the available Delta+1 colors, then almost certainly a (Delta + 1) coloring can be found using only the sampled colors. We then show that this palette sparsification theorem naturally leads to essentially optimal sublinear algorithms in the above-mentioned models of computation.
Based on joint work with Yu Chen and Sanjeev Khanna.
Prof. Mark Zhandry (Princeton University)
Quantum Lightning Never Strikes the Same State Twice
Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, we investigate quantum lightning, where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results:
- We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local.
- We give Either/Or results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this suggests that natural schemes do attain strong security guarantees.
- We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC'12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our Either/Or result for signatures, giving the first separation between two security notions for signatures from the literature.
- Finally, we give a plausible construction for quantum lightning, which we prove secure under an assumption related to the multi-collision resistance of degree-2 hash functions. Our construction is inspired by our Either/Or result for hash functions, and yields the first plausible standard model instantiation of a non-collapsing collision resistant hash function. This improves on a result of Unruh [Eurocrypt'16] which is relative to a quantum oracle.
Prof. Omri Weinstein (Columbia University)
Lower Bounds for Oblivious Near-Neighbor Search
We prove an ~Omega(d*log n) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the d-dimensional Hamming cube. For the natural setting of d =~ (log n), our result implies a ~ log^2(n) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound known for ANN. This is the first super-logarithmic *unconditional* lower bound for ANN against general (non black-box) data structures.
We also show that any oblivious static data structure for decomposable Search problems (like ANN) can be obliviously "dynamized" with O(log n) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).
Joint work with Kasper Green Larsen, Tal Malkin and Kevin Yeo.