## THEORY CANAL: The Rochester Theory Seminar Series 2018-2019 |

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) are from 12:00PM to 12:55PM. (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 meetings this year will be held (except as noted otherwise below) in Room GOL-2500, 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 Golisano Hall (still called "Building 70" in some places) is.)

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

Theory Canal is organized this year by Ivona Bezáková of RIT, Daniel Štefankovič of UR, and David Narváez and Wenbo Sun of RIT as the "theory elves". If you have any questions, please send email to "ib" (in the domain cs.rit.edu), "stefanko" (in the domain cs.rochester.edu), or "den9562" or "ws3109" (in the domain rit.edu).

**August 22, 2018 12:00 - 1:30PM**, Room:**GOL-2455**(please note the longer time slot to accommodate two shorter talks, and the non-standard location)

*Speakers*:**Sujoy Sikdar, Sibel Adali, and Lirong Xia (RPI)**

*Topic*:**Mechanism Design for Multi-Type Resource Allocation***Abstract*: We consider multi-resource allocation problems where there are multiple types of items, and a collection of agents must be allocated bundles consisting of multiple types of resources given their preferences over such bundles.First, we consider the problem of multi-type housing markets where the resources are initially endowed to the agents, and the goal is to redistribute the resources given agents' preferences. Our main contribution is an extension of the Top-Trading-Cycles (TTC) mechanism which is strict core selecting for markets where agents may be endowed and allocated with multiple resources of each type. The strict core is a natural and intuitively stable notion of a good redistribution: an allocation is in the strict core when no group of agents have an incentive to deviate by exchanging their initial endowments in a manner which benefits every agent int he group. When agents may be endowed and allocated with multiple resources, strict core allocations are not guaranteed to exist. We generalize the results of recent works by Fujita et al. (2015) and Sikdar et al. (2017) which extend the TTC mechanism to select strict core allocations under different restrictions on agents' preferences along two dimensions: First, our setting is more general than multi-type housing markets(Moulin 1995;Sikdar et al. 2017} and the setting of Fujita et al. (2015). Second, our extension of TTC is strict core selecting under the weaker restriction on preferences of strict CMI-trees, which we introduce as a new preference language that generalizes commonly-studied language such as generalized lexicographic preferences and LP-trees. We introduce an even more general setting of housing markets with acceptable bundles (HMABs) where agents may specify arbitrary sets of acceptable bundles as a generalization of multi-type housing markets, and extend the TTC mechanism to HMABs. Our main result is that for any instance of housing markets with acceptable bundles, and any CMI-tree profile, if TTC outputs an acceptable full allocation, then TTC is strict core selecting and non-bossy.

Second, we focus on the allocation problem where there multiple types of resources, and consider a large and flexible class of sequential mechanisms that are composed of local mechanisms, one for each type, that decided the allocation of resources of that type. Often, different agencies are responsible for the allocation of different types of items. In this work, we address the following main questions: How should the designers in the different agencies choose mechanisms in order for the final allocation of items of all types to satisfy desirable normative properties? On the other hand, if a central planner wants the final allocation to satisfy certain desirable properties, how does it constraint the mechanisms that can be used by the individual agencies? Our main result is a characterization of strategyproof and non-bossy sequential mechanisms under the lexicographic preference domain.

AND*Speakers*:**Jun Wang, Sujoy Sikdar, Lirong Xia (RPI), and Hadi Hosseini (RIT)**

*Topic*:**Envy-Free Allocation of Indivisible Items, its Relaxation and open questions***Abstract*: Envy-freeness (EF) is a natural notion of the fairness of an allocation, where every agent prefers her own bundle of items at least as much as any other agents' bundle. In this work, we focus on the setting of the fair division of indivisible items, where each item should be given entirely to a single agent given their preferences. Unfortunately, in this setting an envy-free allocation is not guaranteed to exist. Motivated by this, Budish (2011) introduced the notion of envy-freeness bounded by one good (EF1), as a relaxation of envy-freeness. An allocation satisfies EF1, if whenever an agent envies an other agent, the envy can be eliminated by removing an item from the other agents' bundle. Recently, there has been growing interest in a hierarchy of relaxations of envy-freeness, with the strongest being envy-freeness up to any good (EFX)(Caragiannis et al. 2016) where envy is eliminated by the removal of any good. However, the existence of EFX for even certain restrictions on preferences is an open question.In this work, we focus on the following question: What are natural relaxations of envy-freeness, and when can we design mechanisms which guarantee bounded envy along with other desirable properties? We show that an EFX allocation is guaranteed to exist, and characterize mechanisms satisfying EFX, strategyproofness, and neutrality under the lexicographic preference domain as a serial dictatorship. More generally, we define new, and natural relaxations of envy-freeness, and study their existence, and compatibility of such allocations under natural restrictions on agents' preferences.

**September 12, 2018 12:00PM**

*Speaker*:**Daniel Štefankovič (UR)**

*Topic*:**The complexity of approximating the matching polynomial in the complex plane***Abstract*: We study the problem of approximating the value of the matching polynomial on graphs with edge parameter gamma, where gamma takes arbitrary values in the complex plane. When gamma is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of gamma, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Delta as long as gamma is not a negative real number less than or equal to -1/(4(Delta-1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Delta >= 3 and all real gamma less than -1/(4(Delta-1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Delta with edge parameter gamma is #P-hard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real gamma it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of gamma values on the negative real axis. Nevertheless, we show that the result does extend for any complex value gamma that does not lie on the negative real axis. Our analysis accounts for complex values of gamma using geodesic distances in the complex plane in the metric defined by an appropriate density function. Joint work with Ivona Bezáková, Andreas Galanis and Leslie Ann Goldberg.**September 19, 2018 12:30PM**[Note: non-standard parity Wednesday and non-standard location; there will be no talk on Sept 26]

*Speaker*:**Antonio Blanca, Penn State**

*Topic*:**The Swendsen-Wang algorithm for the Ising model**

*Location*:**Wilson 121, UR***Abstract*: Markov chain Monte Carlo (MCMC) methods are powerful algorithms for sampling from complex probability distributions. In this talk, we analyze a popular MCMC algorithm, known as the Swendsen-Wang dynamics, for the Ising model on a graph G = (V,E). This model is among the most important and classical of all Markov random fields, with many applications in statistical physics, computer vision, and machine learning.The Swendsen-Wang dynamics is a global Markov chain which is conjectured to converge to equilibrium in O(|V|^0.25) steps on any graph for all values of the temperature parameter β. It was recently established that this dynamics converges in polynomially many steps on all graphs at all temperatures, yet there are few results providing o(|V|) upper bounds on its convergence time. In this talk, we present a new result concerning the speed of convergence of the Swendsen-Wang dynamics on general graphs. In particular, when β < β_c(d), where β_c(d) denotes the uniqueness/non-uniqueness threshold on infinite d-regular trees, we prove that the relaxation time of the Swendsen-Wang dynamics is Θ(1) on any graph.

**October 10, 2018 12:00PM**

*Speaker*:**David E. Narvaez, Rochester Institute of Technology**

*Topic*:**A Formally Verified Symmetry Breaking Tool for SAT***Abstract*: The Boolean satisfiability problem (SAT) remains a central problem to theoretical as well as practical computer science. Recently, the need to trust the results obtained by SAT solvers has led to research in formalizing these. Nevertheless, tools in the ecosystem of SAT problems (such as preprocessors, model counters, etc.) would need to be verified as well in order for the results to be trusted. One family of tools that has proven to be crucial in tackling hard problems via SAT is symmetry breaking tools. Our research seeks to obtain a verified symmetry breaking tool for SAT by formalizing Crawford's symmetry breaking idea.**October 24, 2018 12:00PM**

*Speaker*:**Laasya Bangalore (UR)**

*Topic*:**Almost-Surely Terminating Asynchronous Byzantine Agreement***Abstract*: The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavors of termination guarantee - with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting.**November 14, 2018 12:00PM**

*Speaker*:**Andrew Searns (RIT)**

*Topic*:**On Counting Oracles for Path Problems***Abstract*: We initiate the study of counting oracles for various path problems in graphs. Distance oracles have gained a lot of attention in recent years, with studies of the underlying space and time tradeoffs. For a given graph G, a distance oracle is a data structure which can be used to answer distance queries for pairs of vertices s, t in V(G). In this work, we extend the set up to answering counting queries: for a pair of vertices s and t, the oracle needs to provide the number of (shortest or all) paths from s to t. We present O(n^{1.5}) preprocessing time, O(n^{1.5}) space, and O(n^{0.5}) query time algorithms for oracles counting shortest paths in planar graphs and for counting all paths in planar directed acyclic graphs. We extend our results to other graphs which admit small balanced separators and present applications where our oracle improves the currently best known running times. (Joint work with Ivona Bezáková, to appear at ISAAC '18.)**November 28, 2018 12:00PM**

*Speaker*:**Antigoni Polychroniadou**

*Topic*:**Limits of Practical Sublinear Secure Computation***Abstract*: Secure computations on big data call for protocols that have sublinear communication complexity in the input length. While fully homomorphic encryption (FHE) provides a general solution to the problem, employing it on a large scale is currently quite far from being practical. This is also the case for secure computation tasks that reduce to weaker forms of FHE such as ''somewhat homomorphic encryption'' or single-server private information retrieval (PIR).Quite unexpectedly, Aggarwal, Mishra, and Pinkas (Eurocrypt 2004), Brickell and Shmatikov (Asiacrypt 2005), and shelat and Venkitasubramaniam (Asiacrypt 2015) have shown that in several natural instances of secure computation on big data, there are practical sublinear communication protocols that only require sublinear local computation and minimize the use of expensive public-key operations. This raises the question of whether similar protocols exist for other natural problems.

In this talk I am going to present a framework for separating ''practical'' sublinear protocols from ''impractical'' ones, and establish a methodology for identifying ''provably hard'' big-data problems that do not admit practical protocols. This is akin to the use of NP-completeness to separate hard algorithmic problems from easy ones. We are going to show that while the previous protocols of Aggarwal et al., Brickell and Shmatikov, and shelat and Venkitasubramaniam are indeed classified as being ''practical'' in this framework, slight variations of the problems they solve and other natural computational problems on big data are hard.

Joint work with Elette Boyle and Yuval Ishai

**December 12, 2018 (No meeting; RIT Finals)****Spring semester 2019:**Most members of the theory group are traveling extensively this term, hence our meetings are more sporadic and on atypical dates/times.**March 6, 2019 12:15PM, room GOL-2500**- note atypical date and time (later than usual and earlier than originally announced...)

*Speaker*:**Ivona Bezáková (RIT)**

*Topic*:**Inapproximability of the independent set polynomial in the complex plane***Abstract*: This talk will discuss the complexity of approximating the value of the independent set polynomial Z_G(\lambda) of a graph G with maximum degree \Delta when the activity \lambda is a complex number. For positive real \lambda, the independent set polynomial is the partition function of the hardcore model, a model from statistical physics which aims to sample independent sets in G, where an independent set I is chosen with probability proportional to \lambda^{|I|}. Connections with Lovász local lemma led to interest in negative values of \lambda, and the existence of FPTAS (fully polynomial time approximation scheme) for some complex \lambda's led to studies of the entire complex plane. This talk will survey both positive and negative results in this area, focusing on provable inapproximability of the independent set polynomial for \lambda in a large previously defined region in the complex plane.Joint work with Andreas Galanis, Leslie Goldberg, and Daniel Štefankovič.

**March 13, 2019 (No meeting; UR/RIT Spring Break)****March 27, 2019 12:00PM**

*Speaker*:**TBA**

*Topic*:**TBA***Abstract*: TBA**April 10, 2019 12:00PM**

*Speaker*:**TBA**

*Topic*:**TBA***Abstract*: TBA**April 24, 2019 12:00PM**

*Speaker*:**Andrew Read-McFarland (UR)**

*Topic*:**TBA***Abstract*: TBA