School of Mathematics

Quantum Fingerprints that Keep Secrets

Dmitry Gavinsky
NEC Research Laboratories
April 18, 2011

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that classically this is not achievable; our construction is quantum, and it gives a new example of (unconditional) qualitative advantage of quantum computers.

Graph Sparsification by Edge-Connectivity and Random Spanning Trees

Nick Harvey
University of Waterloo
April 11, 2011

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc. Batson, Spielman and Srivastava (2009) showed that sparsifiers with O(n/eps^2) edges exist, and they can be computed in time poly(n,eps).

"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consist

Menachem Kojman
Ben Gurion University of the Negev; Member, School of Mathemtics
April 6, 2011

MATHEMATICAL CONVERSATIONS

"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consistency." -- Andre Weil