# 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
February 3 No seminar
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
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) An Improved Distributed Algorithm for the Maximal Independent Set Problem
April 6, 10-11:30 a.m. in 222 IST Tim Roughgarden (Stanford) How Computer Science Informs Modern Auction Design
April 7 Mahdi Belbasi (PSU) Saving Space by Algebraization
April 14 Om Thakkar (PSU) A brief introduction to Concentrated Differential Privacy
April 21 No seminar
April 21 Ishan Behoora (PSU) Near straight line trajectories
• 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.

## An Improved Distributed Algorithm for the Maximal Independent Set Problem

A maximal independent set (MIS) in a given undirected graph $G=(V,E)$ is an independent set I whose size cannot be increased by addition of a new vertex from $V \backslash I$. In the study of distributed algorithms, finding an MIS is a fundamental problem.

In this talk, I will present and analyze a distributed algorithm for the MIS problem due to Ghaffari (SODA’14). This algorithm works in the LOCAL model of distributed computing. In the LOCAL model, each vertex knows only its neighbors and in each communication round, a vertex can only 1) exchange information with its neighbors, and 2) perform local computations. The algorithm due to Ghaffari is randomized and it runs in $O(\log d_{max} + 2\sqrt{\log \log n})$ rounds with high probability, where $d_{max}$ denotes the maximum degree of the input graph and $n$ denotes the size of $V$.

## How Computer Science Informs Modern Auction Design

Economists have studied the theory and practice of auctions for decades. How can computer science contribute? Using the ongoing U.S. FCC double-auction for wireless spectrum as a case study, I'll illustrate the many answers: novel auction formats, algorithms for NP-hard problems, approximation guarantees for simple auctions, and communication complexity-based impossibility results.

## Saving Space by Algebraization

Space optimization is a crucial aspect of algorithm design, since in several scenarios space is a more valuable resource than time. This raises the question of whether there are general techniques to reduce the space complexity of algorithms.

It is known that several NP-complete problems have dynamic programming algorithms with super-polynomial space complexity. In this talk, I will present a framework that, given such a dynamic programming algorithm (satisfying some additional conditions), gives another algorithm that uses only polynomial space. This technique can be applied to several fundamental problems including Subset Sum, Knapsack problem, Traveling Salesman problem, Steiner Tree problem and Set Cover. I will also discuss two of the above applications.

Based on “Saving Space by Algebraization” by D. Lokshtanov and J. Nederlof (STOC ‘10).

## A brief introduction to Concentrated Differential Privacy

Concentrated differential privacy (CDP) was recently introduced by Dwork and Rothblum as a relaxation of differential privacy. It permits a sharper analysis of the privacy loss of many basic algorithms, including a tight analysis of the well-known Gaussian mechanism for noise addition. In this talk, we present a formulation of CDP, called zero-concentrated differential privacy (zCDP), due to Bun and Steinke. We show why the Gaussian mechanism satisfies zCDP, and some of the relations between zCDP and the traditional notions of pure and approximate differential privacy.

Based on the paper titled "Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds" by Mark Bun and Thomas Steinke.

## Near straight line trajectories

Often while tracking players in a sport environment such as soccer there is a need for determining when players move within "near" straight lines. Within the field this corresponds to an unobstucted movement. We look at approaches to quantify this and the challenges inherent within metrics we choose and the progress made on it so far while trying to treat this within a rigorous framework. And the theoretical challenges we have dependant on the metric chosen.