CS Theory/Math Seminar


Organizers: Venkata Gandikota and Elena Grigorescu

This semester the seminar is scheduled on Mondays 1:30-2:30 pm, and will alternate with the reading group. Please check the calendar for the exact details. To get announcement before the talk, please also join our mailing list. You might also wish to sign up for the reading group.

Schedule, Fall 2015

Monday Sep 21

Elena Grigorescu

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

David Gleich

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.

Joint work

Mon Oct 19

Hemanta Maji

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.

Joint work

Mon Nov 9

Wojciech Szpankowski

1:30pm, Stewart Center's Fowler Hall Arden L. Bement Jr. Distinguished Lecture

Mon Nov 23

Venkata Gandikota

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

Edinah Gnang

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. <html>