Theoretical CS Reading Group

The reading group meets once a week usually, Monday 1:30-2:30pm to discuss a particular paper or topic.

Please join our mailing list to get notifications about the weekly meetings and discussions.

Fall 2017
Spring 2017
Fall 2016
Spring & Summer 2016
Fall 2015
Spring & Summer 2015
Fall 2014
Spring 2014
Summer & Fall 2013

Fall 2015

Thursday, 17th Sept 2015 — O. Goldreich, D. Ron, "Sample based testing of Graph Properties"
Presenter: Akash Kumar

Monday, 21st Sept 2015 — Theory Seminar - Prof. Elena Grigorescu, Purdue University
Local Testing of Lattices

Monday, 28th Sept 2015 — Counting Types of Markov Fields
Presenter: Abram Magner

Monday, 5th Oct 2015 — Theory Seminar - Prof. David Gleich, Purdue University
Network Clustering with Higher-Order Structures

Click to view 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.

Friday, 16th Oct 2015— M. Crouch, D. Stubbs, "Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching"
Presenter: Samson Zhou

Monday, 19th Oct 2015 — Theory Seminar - Prof. Hemanta Maji, Purdue University
Secure Computation using Imperfect Building Blocks

Click to view 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

Monday, 26th Oct 2015— Chitnis,, "Kernelization via Sampling with Applications to Dynamic Graph Streams"
Presenter: Negin Karisani

Monday, 23rd Nov 2015— Bridging Computation on Lattices and Codes
Presenter: GV

Monday, 30th Nov 2015— Scarf's Lemma and Its Application
Presenter:Young-San Lin

Thursday, 12th Dec 2015 — Theory Seminar - Prof. Edinah Gnang, Purdue University
On the spectra of direct sums and Kronecker products of side length 2 hypermatrices and related algorithmic problems in data science

Click to view 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.