Organizers: Venkata Gandikota and Elena Grigorescu
Monday Sep 21
LWSN 3102, 1:30-2:30pm. Title: Local Testing of Lattices
Abstract: We initiate a systematic study of local testing for membership in lattices. We describe canonical testers for lattices and show upper and lower bounds for testing specific families of lattices.
Based on joint work with Karthik Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota
Mon Oct 5
LWSN 3102, 1:30-2:30pm. Title: Network clustering with higher-order structure
Abstract: We'll discuss a new generalization of the Cheeger inequality to higher-order structures in networks including network motifs. This is easy to implement and seemlessly generalizes spectral clustering to directed, signed, and many other types of complex networks. In particular, our generalization allow us to re-use the large history of existing ideas in spectral clustering including local methods, overlapping methods, and relationships with kernel k-means.
Mon Oct 19
LWSN 3102, 1:30-2:30pm. Title: Secure Computation using Imperfect Building Blocks
Abstract: Secure multi-party computation enables mutually distrusting parties to compute over their private data. Such secure computation protocols leverage the security of atomic ``building blocks'' to perform complex computations privately. The security of these protocols crucially hinges on the assumption that these underlying building blocks have perfect security. Even minor imperfections in these building blocks can violate the security of these protocols. This raises the following important question: ``Can secure computation be based on imperfect building blocks?'' In this talk, I will present algorithmic solutions that resolve this question in the affirmative.
Mon Nov 9
1:30pm, Stewart Center's Fowler Hall Arden L. Bement Jr. Distinguished Lecture
Mon Nov 23
1:30pm Title: Deciding orthogonality in Construction-A lattices. And more.
Abstract: We show a structural property of orthogonal Construction-A lattices, and a simple algorithm for deciding orthogonality based on this property.
Joint work with Karthik Chandrasekaran and Elena Grigorescu
Thrs Dec 10
12:15pm Title : On the spectra of direct sums and Kronecker products of side length 2 hypermatrices and related algorithmic problems in data science.
Abstract: We present elementary method for obtaining the spectral decomposition of hypermatrices generated by arbitrary combinations of Kronecker products and direct sums of cubic hypermatrices having side length 2. The method is based on a generalization of Parsevalís identity. We use the general formulation of Parsevalís identity to introduce hypermatrix Fourier transforms and discrete Fourier hypermatrices. We extend to hypermatrices orthogonalization procedures and Sylvesterís classical Hadamard matrix construction. We conclude the talk with illustrations of spectral decompositions of adjacency hypermatrices of finite groups and a proof of a hypermatrix Rayleigh quotient inequality.
This is a joint work with Yuval Filmus.
Link to schedule for Spring 2015 Fall 2014. Spring 2014, Fall 2013. Spring 2013. Fall 2012.