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

DateSpeakerTitle
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) Parameterized Property Testing of Functions
March 3 Roksana Baleshzar (PSU) Optimal Unateness Testers
March 10 Spring break, no seminar TBD
March 17, 10-11 a.m. in 223B IST Jiayu Zhang (PSU) CSS codes for quantum error correction
March 24 Nithin Varma (PSU) A polylogarithmic space deterministic streaming algorithm for estimating the distance to sortedness
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
• Talks will generally be held on Fridays from 12:10-1:10 p.m. in 118 Earth and Eng Sciences Building (unless they are part of the departmental colloquium, in which case they will be held from 2-3 p.m. in 113 IST Building (Cybertorium)). Any unusual date/time/location is highlighted in the schedule.
• If you would like to speak, please email us at: theory [at] cse [dot] psu [dot] edu.
• If you want to receive announcements of upcoming talks, please join the theory mailing list.
Archives

## 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 https://arxiv.org/pdf/0911.1696.pdf ).

## Parameterized Property Testing of Functions

The complexity of sublinear-time algorithms is usually parameterized in terms of the size of the input. However, there is evidence that the input size is not always the best parameter to express the complexity. Consider, for example, the problem of testing sortedness of arrays, where one has to decide with high probability, using a small number of queries, if the array is in sorted order, or a large fraction of array elements need to be modified to make it sorted. For testing sortedness of arrays of length $n$, the query complexity is $\Theta(\log n)$ when the array values are real, and constant when the values are Boolean.

We investigate the parameters in terms of which the complexity of property testing algorithms, and more generally, sublinear-time algorithms, should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to circumvent the (worst-case) lower bounds, expressed in terms of the input size, for several problems.

In this talk, I will present a property tester for sortedness of arrays, that makes $O(\log r)$ queries, where $r$ is an upper bound on the number of distinct values in the array. This result circumvents the $\Omega(\log n)$ lower bound due to Fischer (Inf. Comput., 2004).

Based on joint work with Sofya Raskhodnikova and Nithin Varma (ITCS 2017).

## Optimal Unateness Testers

We study the problem of testing whether a given real-valued function $f$ on domain $[n]^d$ (where $n,d \in N$) is unate. A function $f:[n]^d \rightarrow R$ is unate if for every coordinate the function is either nonincreasing or nondecreasing. For the special case, a function $f:[n]^d \rightarrow R$ is monotone if for all coordinate the function is either nondecreasing. A tester has to accept the input function with probability at least 2/3 if it unate and reject the function with probability at least 2/3 if it is far from being unate. A function is far from unate if we need to change it in many places to make it unate. Eventhough, there are lots of work on testing monotonicity, there were just a few work on testing unate property. And also no lower bound were known for unateness. In this talk, we give a $O(d \log d)$-query nonadaptive unateness tester and also $O(d)$- query adaptive unateness tester. We also show that both of these testers are optimal. This result show that adaptivity helps in testing unateness of real valued functions on the domain $[n]^d$. However, this is in contrast to the situation for monotonicity testing where there is no adaptivity gap for the same kind of function.

Based on Joint work with: Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and C. Seshadhri.

## CSS codes for quantum error correction

How can we encode and store quantum information in a register of qubits so that even if some qubits of the encoding are corrupted, we can still recover the original information? In classical computing, the design of error-correcting codes is simplified by the fact that errors are discrete. But in quantum computing, things are more complicated: there are infinitely many possible errors, even if only a small number of qubits are affected.

In this lecture we will review the classical linear codes and some basics of quantum computing, then introduce the construction and error correction procedures of Calderbank-Shor-Steane (CSS) codes. We will describe a specific code, called the Steane code. Finally, we will prove that CSS codes can correct low-weight "Pauli errors", and explain why this is sufficient for correcting arbitrary low-weight quantum errors.

This lecture is based on the Chapter 10 of “Quantum Computation and Quantum Information” by Nielsen and Chuang.

## A polylogarithmic space deterministic streaming algorithm for estimating the distance to sortedness

Given a sequence of numbers, its distance to sortedness is defined as the size of the smallest set of elements whose deletion leaves a non-decreasing sequence. This quantity can be computed exactly in time $O(n \log n)$ using a dynamic programming algorithm. In this talk, I will present a deterministic streaming algorithm due to Naumovitz and Saks (SODA 2015) for computing the distance to sortedness approximately. The algorithm, for every fixed $\epsilon > 0$, approximates the distance to sortedness of a stream of numbers to within a factor of $(1 + \epsilon)$ by making only one pass over the input stream. Its space complexity is polylogarithmic in the length of the stream.