Theoretical Computer Science Group

Theory Seminar Schedule for Spring 2017

The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.

January 20 Martin Furer (PSU) Multi-Clique-Width, a Powerful New Width Parameter
January 27 No seminar TBD
February 3 No seminar TBD
February 10 Jalaj Upadhyay (PSU) Fast and Space-Optimal Differentially-Private Low-Rank Factorization in the General Turnstile Update Model
February 17 Eunou Lee Quantum Lovasz Local Lemma
February 24 Ramesh Krishnan (PSU) TBD
March 3 Roksana Baleshzar (PSU) TBD
March 10 Spring break, no seminar TBD
March 17 Jiayu Zhang (PSU) TBD
March 24 Nithin Varma (PSU) TBD
March 31 Meiram Murzabulatov (PSU) TBD
April 7 Mahdi Belbasi (PSU) TBD
April 14 Om Thakkar (PSU) TBD
April 21 Mark Bun (Princeton) TBD
April 21 Ishan Behoora (PSU) TBD

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014     Spring 2015     Fall 2015     Spring 2016     Fall 2016

Multi-Clique-Width, a Powerful New Width Parameter

Multi-clique-width is a width parameter for graphs. It is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the size of a maximum independent set (or even the independent set polynomial) or computing the chromatic number. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs.

Tree-width and clique-width will be introduced.

Based on the ITCS 2017 paper: "Multi-Clique-Width."

Fast and Space-Optimal Differentially-Private Low-Rank Factorization in the General Turnstile Update Model

The problem of ${\em low-rank factorization}$ of an mxn matrix A requires outputting a singular value decomposition: an $m x k$ matrix $U$, an $n x k$ matrix $V$, and a $k x k$ diagonal matrix $D$) such that $U D V^T$ approximates the matrix $A$ in the Frobenius norm. In this talk, we study releasing differentially-private low-rank factorization of a matrix in the general turnstile update model. We give a differentially-private algorithm instantiated with respect to a privacy level stronger than privacy levels for this and related problems studied in previous works, namely that of Blocki ${\text{\it et al.}}$ (FOCS 2012), Dwork ${\text{\it et al.}}$ (STOC 2014), Hardt and Roth (STOC 2012, STOC 2013), and Hardt and Price (NIPS 2014). We consider two matrices A and A' as neighboring if A - A' can be represented as an outer product of two unit vectors. Our private algorithm with respect to this privacy level incurs optimal additive error. We also prove a lower bound that shows that the space required by this algorithm is optimal up to a logarithmic factor.

Based on the paper arXiv:1604.01429 .

Quantum Lovasz Local Lemma

If each event occurs with probability less than 1 and all events are mutually independent, then, with positive probability, none of the events will happen. Lovasz Local Lemma relaxes this condition slightly: if the events are “mostly” independent and each event happens with “not too high” probability, then, with positive probability, none of the events will happen. Formally, let $B_1, B_2,…,B_n$ be events with $\Pr(B_i)\leqp$ that are mutually independent of all but d of others. If $p*e*(d+1)<1$, then $\Pr(\text{none of the events happens})>0$.

In this talk, a quantum (or rather linear algebraic) analogue of this lemma will be presented. Namely, let $X_1, X_2,…,X_n$ be subspaces such that each subspace is mutually “independent" of all but d of the others. If each space doesn’t “occupy” the whole space too much then the intersection of $X_i$’s is not empty. We will clarify and prove this statement in this talk.

This talk will be based on "A Quantum Lovasz Local Lemma” by Ambainis, Kempe, and Sattath (see ).