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

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:20PM to 1:15PM. (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 GOL-1445, Golisano Hall (still called "Building 70" in some places), Golisano College of Computing and Information Sciences, Rochester Institute of Technology, Rochester, NY 14623.

The Spring Meetings this year will be held 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 David Narváez 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), "den9562" (in the domain rit.edu), or "lane" (in the domain cs.rochester.edu).

**Monday, September 4 (Labor Day), 9AM-5PM JOEL I. SEIFERAS RETIREMENT CELEBRATION AT THE UNIVERSITY OF ROCHESTER: JoelFest: A Day of Talks by Zvi Galil, Shafi Goldwasser, Jon Kleinberg, and Muthuramakrishnan Venkitasubramaniam**9:00 -10:00 Zvi Galil; talk title: *Online Revolutions: From Stringology with Joel to Georgia Tech's Highly Affordable Master Degree.*10:00 -10:30 Break. 10:30 -11:30 Jon Kleinberg; talk title: *Social Dynamics and Mathematical Inevitability*.11:30 -2:30 Free Time for Lunch (see the Lunch Break section on this page). 2:30 -3:30 Shafi Goldwasser; tentative talk title: *Crypto Computing*.3:30 -4:00 Break. 4:00 -5:00 Muthuramakrishnan Venkitasubramaniam; talk title: *The Status of Zero-Knowledge Proofs*.More information at http://www.cs.rochester.edu/u/lane/=joelfest/

**September 13, 2017 12:20PM**

*Speaker*:**Stanisław P. Radziszowski, RIT**

*Topic*:**Computers in Ramsey Theory: Testing, Constructions and Nonexistence***Abstract*: Ramsey theory is often regarded as the study of how order emerges from randomness. While originated in mathematical logic, it has applications in geometry, number theory, game theory, information theory, approximation algorithms, and other areas of mathematics and theoretical computer science.Ramsey theory studies the conditions of when a combinatorial object necessarily contains some smaller given objects. The central concept in Ramsey theory is that of arrowing, which in the case of graphs describes when colorings of larger graphs necessarily contain monochromatic copies of given smaller graphs. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory, always involving arrowing. The determination of whether this arrowing holds is notoriously difficult, and thus it leads to numerous computational challenges concerning various types of Ramsey numbers and closely related Folkman numbers.

This talk will overview how computers are increasingly used to study the bounds on Ramsey and Folkman numbers, and properties of Ramsey arrowing in general. This is happening in the area where traditional approaches typically call for classical computer-free proofs. It is evident that now we understand Ramsey theory much better than a few decades ago, increasingly due to computations. Further, more such progress and new insights based on computations should be anticipated.

**September 27, 2017 12:20PM**

*Speaker*:**Peizhao Hu, RIT**

*Topic*:**Outsourced Decision Tree Evaluation with Low-Round Complexity***Abstract*: Decision tree is one of the widely-used classification techniques in many application domains, such as medical diagnosis. In a two-party setting, the server has a trained model, while the client supplies inputs to the server for classification; both parties might not want to share their sensitive data due to privacy concerns. Recent studies showed constructions of secure two-party protocols for decision tree evaluation without disclosing one party's private data to another using homomorphic encryption. In this talk, we focus on private evaluation of decision tree in an outsourcing setting in which the expensive homomorphic operations are delegated to the cloud. We show the construction of a secure comparison circuit using homomorphic addition and multiplication. This comparison circuit allows our protocol to achieve lower-round complexity compared to the recent work. We also discuss the use of the key-homomorphic property to support computations on data encrypted using different public-key pairs, and construct a hybrid encryption scheme that leverages a block-cipher to reduce communication overhead. Finally, we analyze the security of the proposed protocol and discuss its computation and communication complexity.**October 11, 2017 12:20PM**

*Speaker*:**Daniel Stefankovic, UR****November 8, 2017 12:20PM (Postponed from October 25)**

*Speaker*:**Hadi Hosseini, RIT****November 22, 2017 (No meeting; Thanksgiving)****December 13, 2017 (No meeting; RIT Finals)****January 10, 2018 (No meeting; UR/RIT Break)****January 24, 2018****February 14, 2018****February 28, 2018****March 14, 2018 (No meeting; UR/RIT Spring Break)****March 28, 2018****April 11, 2018: Canceled****April 25, 2018****Thursday, May 3, 2018, 11AM***Speaker*:**Lirong Xia, RPI**

*Abstract*:
We study the structure learning problem for graph homomorphisms,
commonly referred to as H-colorings, including the weighted case which
corresponds to spin systems with hard constraints. The learning
problem is as follows: for a fixed (and known) constraint graph H with
q colors and an unknown graph G=(V,E) with n vertices, given uniformly
random H-colorings of G, how many samples are required to learn the
edges of the unknown graph G? We give a characterization of H for
which the problem is identifiable for every G, i.e., we can learn G
with an infinite number of samples. We focus particular attention on
the case of proper vertex q-colorings of graphs of maximum degree d
where intriguing connections to statistical physics phase transitions
appear. We prove that when q>d the problem is identifiable and we can
learn G in poly(d,q)×O(n^2*log n) time. In contrast for
soft-constraint systems, such as the Ising model, the best possible
running time is exponential in d. When
q \leq d
we prove that the problem
is not identifiable, and we cannot hope to learn G. When
q is less than d-sqrt(d)
we prove that even learning an equivalent graph (any graph with the
same set of H-colorings) is computationally hard---sample complexity
is exponential in n in the worst-case. For the q-colorings problem,
the threshold for efficient learning seems to be connected to the
uniqueness/non-uniqueness phase transition at q=d. We explore this
connection for general H-colorings and prove that under a well-known
condition in statistical physics, known as Dobrushin uniqueness
condition, we can learn G in poly(d,q)×O(n^2*log n) time. Joint work
with Antonio Blanca, Zongchen Chen, and Eric Vigoda

*Abstract*:
One of the fundamental problems at the intersection of computer science, economics, and artificial intelligence is allocating a set of indivisible items to a set of self-interested agents. These problems are particularly interesting when mechanism designers wish to satisfy certain desirable properties such as efficiency, fairness, and truthfulness.

In this talk, I will discuss some of the challenges in designing deterministic and randomized matching mechanisms, showing how empirical findings can provide deeper insights into theoretical guarantees. In addition, I will argue how traditional matching mechanisms fail to satisfy desirable properties such as truthfulness in dynamic environments, and discuss a number of open problems in this domain.

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

*Abstract*:
The last two decades have seen extraordinary advances in industrial
applications of constraint satisfaction techniques, while combinatorial
problems have been pushed to the sidelines. We propose a comprehensive
analysis of the state of the art in constraint satisfaction problems when
applied to combinatorial problems in areas such as graph theory, set theory,
algebra, among others. We believe such a study will provide us with a deeper
understanding about the limitations we still face in constraint satisfaction
problems.

*Speaker*: **Andrew Searns, RIT**

*Abstract*:
Counting minimum (s,t)-cuts in general graphs is a #P-complete problem. However, the problem can be solved in polynomial time for planar graphs. Currently the fastest known algorithm runs in time O*(n^2) for a planar graph with n vertices, where the O* notation hides the computational cost needed to mathematically manipulate the number of cuts. In this talk we discuss an approach towards breaking this O*(n^2) time barrier.

This work is supported by the NSF's REU (Research Experiences for Undergraduates) program and is joint work with Ivona Bezakova and Josh Sellers.

*Speaker*: **Tamal Biswas, UR**

*Abstract*:
Human decisions are influenced by various factors, such as risk, uncertainty, time pressure,
and depth of thinking, whereas decisions by an AI agent can be effectively optimal without
these limitations. The concept of depth, a well-defined term in game theory (including chess),
does not have a clear formulation in decision theory. To quantify depth, we can configure an
AI agent of supreme competence to 'think' at depths beyond the capability of any human, and
in the process collect evaluations of decisions at various depths. We formulate a new measure
called 'depth of satisficing' from analyzing the decisions made by humans along with utilizing
computers¿ suggestions for the same set of problems. This formulation combines Herbert
Simon¿s concept of satisficing with aspects of level-k thinking. It augments the statistical
chess model of Regan and Haworth, which provides skill ratings based on the intrinsic quality
of the decisions made.

We use a large dataset from real chess tournaments and evaluations from chess programs (AI agents) of strength beyond all human players. The goal is to transfer the results obtained to other decision-making domains in which effectively optimal judgments can be obtained from either hindsight, answer banks, or powerful AI agents. In some applications, such as multiple-choice tests, we establish an isomorphism of the underlying mathematical quantities, which induces a correspondence between our model and various measurement theories. We present and discuss results showing distinctive human traits that are not demonstrated by computers. We further provide results toward the objective of applying the correspondence in reverse to obtain and quantify the measure of swing, difficulty, discrimination, and complexity for any decision problem.

*Speakers*: **Jackson Abascal and
Shir Maimon, UR
**

*Abstract*:
We establish a number of new results about ranking and compression functions for infinite sets, both in the complexity-theoretic setting and in the recursion-theoretic setting.

This work is joint with Lane A. Hemaspaandra and Daniel Rubery.

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

*Abstract*:
Independence polynomial of a graph $G$ is denoted as $p_G(z)=\sum_{k} c_k z^k$, where $c_k$ is the number of independent sets in graph $G$. Evaluating it at a point gives the number of weighted independent sets of graph $G$ (In particular for $z=1$ this outputs the number of independent sets in $G$). This polynomial is extensively studied for several classes of graphs among which graphs of maximum degree $\Delta$ are one of the most interesting classes. In this case the polynomial approximation (exact evaluation is hard for most of the cases) for real $z$ is well understood. Recently an approximation algorithm using Barvinok's polynomial approximation technique is given for a small region in the complex plane. In this work we want to explore the polynomial approximation for random $\Delta$ regular graph using Barvinok's polynomial approximation technique.

*Abstract*:
Group decision-making is a fundamental challenge in our society, where a group of agents must make a joint decision despite that they have different and conflicting preferences, as in political elections, meta search engines, recommender systems, crowdsourcing, and many other scenarios. Addressing challenges in group decision-making requires considerations from statistics, economics, and computation.

I will give a brief overview of our recent work in developing and leveraging AI techniques to help human beings and software agents make better group decisions, by bridging theory, practice, and education. The main theme is well aligned with the vision set by The One Hundred Year Study on Artificial Intelligence, that "the field of AI is shifting toward building intelligent systems that can collaborate effectively with people, and that are more generally human-aware".