## THEORY CANAL: The Rochester Theory Seminar Series 2016-2017 |

The THEORY CANAL meeting (the Rochester Theory Seminar) is a joint project of the RIT and UR theory groups, and the focus is all areas of theoretical computer science. THEORY CANAL meets (when RIT and UR classes are in session) on the second and fourth Wednesdays of each month. (Due to slot demand, school holidays, and religious holidays, there are some exceptions to that rule. Please see the schedule below for the actual dates.) The talks (exceptions if any will be noted in the detailed list below) start at 12:30PM, and typically run 50-60 minutes. (Of course, plans can change and at the start of the year some of the listings may be tentative; so please make sure you are subscribed to the Theory Canal mailing list---how to do so is described below---so that you hear of all changes in speakers/topics/etc.!)

The Fall Meetings this year will be held (except as noted otherwise below) in Room SLA-2150, Louise Slaughter Hall (still called "Building 78" in some places), Center for Integrated Manufactoring Studies (CIMS), Rochester Institute of Technology, Rochester, NY 14623.

The Spring Meetings this year will be held (except as noted otherwise below) in Room GOL-1435, Golisano Hall (still called "Building 70" in some places), Golisano College of Computing and Information Sciences, Rochester Institute of Technology, Rochester, NY 14623.

Directions to RIT and How to Get a (Free!) Visitor's Parking Pass. (Please make sure to get, at the Information Booth from the Campus Security officer who gives you your free parking pass, a map or instructions as to where to properly park using the pass and where Louise Slaughter Hall (still called "Building 78" in some places) is.)

These meetings are open to the public; all are very warmly welcome.

Theory Canal is organized this year by Zack Fitzsimmons of RIT, Edith Hemaspaandra of RIT, and Lane A. Hemaspaandra of UR. If you have any questions, please send email to "eh" (in the domain cs.rit.edu), "zmf6921" (in the domain rit.edu), or "lane" (in the domain cs.rochester.edu).

**September 14, 2016, 12:30pm**

*Speaker*:**Ivona Bezakova, RIT**

*Topic*:**Finding Detours is Fixed-parameter Tractable**

*Abstract*: We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices $s$ and $t$ of a graph $G$, and an integer $k$, the problem Longest Detour asks for an $(s,t)$-path in $G$ that is at least $k$ longer than a shortest $(s,t)$-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time $\exp(O(k)) \cdot \poly(n)$. This matches (up to the base of the exponential) the best algorithms for finding a path of length at least $k$.Furthermore, we study the related problem Exact Detour that asks whether a graph $G$ contains an $(s,t)$-path that is exactly $k$ longer than a shortest $(s,t)$-path. For this problem, we obtain a randomized algorithm with running time about~$2.746^k$, and a deterministic algorithm with running time about $6.745^{k}$, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

This is joint work with Radu Curticapean, Holger Dell, and Fedor Fomin.

**September 28, 2016, 12:30pm***Speaker*:**Carlos Rivero, RIT**

*Topic*:**Approximate Subgraph Matching in Extended Program Dependence Graphs**

*Abstract*: Universities world-wide are experiencing increasing enrollments in computing. All of these students need to take introductory programming courses and demand personalized feedback, explaining what and why they did correctly and incorrectly in their submissions. Providing personalized feedback is becoming challenging due to the limited number of qualified instructors. This is exacerbated in Massive Open Online Courses where an assignment may have hundreds of thousands of submissions. This talk will focus on our method to automatically deliver personalized feedback to a large body of novice students and to assist instructors in assessing Java and Python assignments. The method is based on the typical grading approach of an instructor looking for particular code snippets in student submissions. Patterns represent code snippets of interest and feedback is attached to them. Student submissions are modeled using extended program dependence graphs that combine control and data flows and include information of the operations that are being performed, e.g., accessing an array. Patterns are modeled as subgraphs, and feedback as natural language templates that are instantiated with variable names and constants from submissions. Our method leverages subgraph matching techniques, borrowed from the graph database field, to perform the matching and to provide personalized feedback.**October 12, 2016, 12:30pm**(No meeting; Yom Kippur)**October 26, 2016, 12:30pm**

*Speaker*:**Muthuramakrishnan Venkitasubramaniam, UR**

*Topic*:**On the Power of Secure Two Party Computation**

*Abstract*: Ishai, Kushilevitz, Ostrovsky and Sahai (STOC`07, SIAM JoC 2009) introduced the powerful "MPC-in-the-head" technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a "black-box" way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called oblivious-transfer hybrid model to an adaptive ZK proof for any NP-language, in a "black-box" way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson's 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC`09, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.As our second contribution, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto'90) to obtain black-box constructions of commit-and-prove protocols with the so called input-delayed property where the honest proverâ€™s algorithm does not require the actual statement until the last round. Previous constructions either required more number of rounds or made non-black-box usage of the underlying primitive. We also show how these proofs can improve round complexity of secure computation protocols in the tamper-proof model.

Joint work with Carmit Hazay.

**November 9, 2016, 12:30pm**

*Speaker*:**Holger Spakowski, University of Cape Town**

*Topic*:**On Limited Nondeterminism and ACC Circuit Lower Bounds**

*Abstract*: Williams's celebrated circuit lower bound technique works by showing that the existence of certain small enough nonuniform circuits implies that nondeterministic exponential time can be speeded up in such a way that it implies a contradiction with the nondeterministic time hierarchy.We apply Williams's technique by speeding up instead (i)

*deterministic*exponential-time computations and (ii) nondeterministic exponential-time computations that use only a*limited number of nondeterministic bits*. From (i), we obtain that $EXP \subseteq ACC$ has a consequence that might seem unlikely, while (ii) yields an exponential ACC size-depth tradeoff for $E^{NP[2^{n^{c\delta}}]}$, which is the class of exponential-time computation with access to an NP oracle where the number of oracle queries is bounded.**November 23, 2016**(No meeting; Thanksgiving)**December 14, 2016**(No meeting; RIT Finals, UR Reading Period)**January 11, 2017**(No meeting; RIT Intersession)**January 25, 2017, 12:30pm**

*Speaker*:**David Narvaez, RIT**

*Topic*:**The Opacity of Backbones**

*Abstract*: A backbone of a boolean formula $F$ is a collection $S$ of its variables for which there is a unique partial assignment $a_S$ such that $F[a_S]$ is satisfiable. This paper studies the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values, $a_S$, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone $S$ is intractable. Further, we show that if integer factoring is not merely worst- case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency.This is joint work with Lane A. Hemaspaandra.

**February 8, 2017, 12:30pm**

*Speaker*:**Andreas Galanis, University of Oxford**

*Topic*:**Inapproximability of the independent set polynomial below the Shearer threshold**

*Abstract*: For a graph G, let p_G(lambda)=Sum lambda^|I| where the sum ranges over all the independent sets I of G. For which values of lambda can we approximate p_G(lambda) on graphs G of max degree D?For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at the tree uniqueness threshold from statistical physics, given by lambda_c(D)=(D-1)^(D-1)/(D-2)^D.

For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value q such that every family of events with failure probability at most q and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the value of the independent set polynomial whenever 0>lambda>-lambda*(D).

Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all D>=3, for all lambda<-lambda*(D), it is NP-hard to approximate the independent set polynomial on graphs of maximum degree D, even within an exponential factor. In fact, we now have the following picture for evaluating the independent set polynomial on graphs G of max degree D. (i) For -lambda*(D)

lambda_c(D), the problem is NP-hard to approximate. This is joint work with Leslie Ann Goldberg and Daniel Stefankovic.

**February 22, 2017, 12:30pm**

*Speaker*:**Rupam Acharyya, UR**

*Topic*:**Title: Glauber Dynamics for Spin Systems on Convergent Dense Graph Sequence**

*Abstract*: Abstract: In this work we studied Glauber Dynamics for Ising Model on dense graphs. Lovasz et al. have introduced an object called*Graphon*which is proved to be the limit of convergent sequence of dense graphs. We prove that the Glauber Dynamics for Ising Model with inverse temperature beta has fast mixing on a convergent series of graphs {G_n} if beta < 1/lambda_1(W) and the dynamics is exponentially slow when beta < 1/lambda_1(W), where W is the graphon where {G_n} converges to and lambda_1(W) is the first eigenvalue of the graphon W.Next we moved towards analyzing the Glauber Dynamics for general spin system. For general spin system we will focus on complete graph first. There we proved fast mixing in the so called Uniqueness region and slow mixing in the non-Uniqueness Region. It is yet to figure out the picture in the critical manifold. With this approach our ultimate goal would be to analyze the dynamics for general spin system on a convergent sequence of dense graphs.

**March 8, 2017, 12:30pm***Speaker*:**Hadi Hosseini, RIT**

*Topic*:**Analyzing and Designing Truthful Matching Mechanisms**

*Abstract*: The problem of allocating indivisible goods to a set of self-interested agents in the absence of transferable utilities (such as money) is omnipresent in various resource allocation settings such as assigning shifts to nurses, dormitory rooms to students, and members to subcommittees. These settings leverage techniques from computer science and economics to ensure fairness and efficiency while preventing agents from manipulating the outcomes.In the first part of this talk, I will focus on two widely-studied randomized matching mechanisms for fair allocation of indivisible goods under ordinal preferences, namely Random Serial Dictatorship and Probabilistic Serial rule. I will give an overview of these properties and discuss how empirical results can provide deeper insights into theoretical guarantees, addressing the question of which mechanism to adopt in practice. In the second part, I will talk about sequential matching with dynamic ordinal preferences. I will briefly describe a novel model based on a generic stochastic decision process and show that, in contrast to static settings, traditional approaches are highly susceptible to manipulation in dynamic settings. I will describe how we can restore some of the desired properties by careful consideration of the history of outcomes and how this history-dependent approach impacts efficiency and fairness.

**March 22, 2017***Speaker*:**Dan Rubery, UR**

*Topic*:**Recursion-Theoretic Ranking and Compression**

*Abstract*: For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to Sigma^star? And for which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. The present paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies the question of which sets have, or lack, such functions.This is joint work with Lane A. Hemaspaandra.

**April 12, 2017, 12:30pm**(No meeting; Passover)**April 26, 2017, 12:30pm**

*Speaker*:**Wenbo Sun, RIT**

*Topic*:**Sampling and Counting Independent Sets in Low Average Degree Graphs**

*Abstract*: The problem of sampling and counting various graph structures (e.g. matchings, colorings, independent sets) arises in many scientific areas ranging from computer science to statistical physics, biology, and ecology, to name a few. These problems tend to be computationally difficult for general graphs. However, in practice the input instances often have a more restricted structure: for example, the graphs are typically sparse.This work focuses on the problem of sampling and counting independent sets, which has attracted a lot of attention of theoretical computer science research community. Previous works have shown that the problem is #P-hard, even for bipartite graphs with constant degree bound. Nevertheless, Markov chain techniques can be used to obtain a polynomial-time approximation algorithm with an arbitrarily close guarantee for graphs with maximum degree up to four. The much more complex approach of correlation decay deals with graphs of degree up five, while the problem is known to be inapproximable for graphs with maximum degrees of 25 or more unless RP = NP. The main purpose of this work is to better understand the phase transition of the problem, i.e., the conditions on the input instances that make the problem tractable.

**May 10, 2017, 12:30pm**(No meeting; UR Finals)

**Here are the talk lists for some previous years:**