## THEORY CANAL: The Rochester Theory Seminar Series 2014-2015 |

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 Meetings this year will be held (except as noted otherwise below) in Room GOL-3000 (the third-floor CS conference room), 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.)

The meetings are open to the public; all are very welcome.

(2) **Reply to that message to subscribe.**

(2) **Reply to that message to unsubscribe.**

**September 10, 2014, 12:30pm**

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

*Topic*:**Minimum Planar Multi-Sink Cuts with Connectivity Priors**

*Abstract*: Given is a connected positively weighted undirected planar graph*G*embedded in the plane, a source vertex*s*, and a set of sink vertices*T*. An*(s,T)*-cut in*G*corresponds to a cycle or a collection of edge-disjoint cycles in the planar dual graph*G*that define a planar region containing^{*}*s*but not*T*. A cut with a connectivity prior does not separate the vertices in*T*from each other: we focus on the most natural prior where the cut corresponds to a (simple, i.e., no repeated vertices) cycle in*G*. We present an algorithm that finds a minimum simple^{*}*(s,T)*-cut in*O(n*time for^{4})*n*vertices. To the best of our knowledge, this is the first polynomial-time algorithm for minimum cuts with connectivity priors. Such cuts have applications in computer vision and medical imaging.**September 24 & October 8, 2014**(No meeting; Rosh Hashanah and Sukkot)**October 22, 2014, 12:30pm**

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

*Topic*:**Resettably-Sound Zero-Knowledge from OWF - The Semi Black-Box Way**

*Abstract*: Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell [FOCS' 01] and is a strengthening of the soundness requirement which demands that soundness holds even if the malicious prover is allowed to "reset" and "restart" the verifier. In their work they prove that resettably-sound ZK arguments require non-black-box simulation techniques, and they provide the first construction based on the breakthrough non-black-box technique of Barak [FOCS 01]. All known implementations of Barak's non-black-box technique require non-black-box use of the underlying cryptographic primitive.Very recently, Goyal, Ostrovsky, Scafuro and Visconti [STOC 14] showed an implementation of Barak's technique that needs only black-box access to a collision-resistant hash-function while still having a non-black-box simulator. Such a construction is referred to as semi black-box. From the work of Chung, Pass and Seth [STOC 13], we know that the minimal assumption required for resettably-sound ZK argument is the existence of one-way functions (OWFs). A natural question is whether it is possible to provide a semi black-box construction based on black-box use of OWFs only. In this work we provide a positive answer to this question by providing a semi black-box construction of a resettably-sound zero-knowledge argument based on OWFs.

**November 12, 2014, 12:30pm**

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

*Topic*:**The Enumeration of All (C5,C5,C5;n) Ramsey Colorings**

*Abstract*: A (C5,C5,C5;n)-coloring is a 3-coloring of the edges of a complete graph on n vertices such that there is no monochromatic cycle of length 5 in any of the colors. The Ramsey number R(C5,C5,C5) is the least n such that there is no (C5,C5,C5;n) coloring, and it is known to be 17. This talk details our search for all (C5,C5,C5;n) colorings, some classical subproblems related to this enumeration problem, the characterization of such colorings on 16 vertices and possible directions for future research.**November 26, 2014**(No meeting; Thanksgiving)**December 10, 2014, 12:30pm**

*Speaker*:**Zack Fitzsimmons, RIT**

*Topic*:**Realistic Assumptions for Attacks on Elections**

*Abstract*: We must properly model attacks and the preferences of the electorate for the computational study of attacks on elections to give us insight into the hardness of attacks in practice. Theoretical and empirical analysis are equally important methods to understand election attacks. I discuss my recent work on domain restrictions on partial preferences and on new election attacks. I propose further study into modelling realistic election attacks and the advancement of the current state of empirical analysis of their hardness by using more advanced statistical techniques.**January 14, 2015**(No meeting; RIT Intersession)**January 28, 2015, 12:30pm**

*Speaker*:**Daniel Stefankovic, UR**

*Topic*:**Spin models: connections between complexity, phase transition, belief propagation, and induced matrix norms**

*Abstract*: What are the typical configurations of a spin model (for example, Ising model, or Potts model) on a random regular graph? We show that the answer to this question is characterized by tree recursions (belief propagation) and p->q operator matrix norms.Understanding the typical configurations allows us to show hardness of approximating the partition function for certain multispin models (for example, Potts model) on d-regular graphs in the non-uniqueness regime (that is, when the Gibbs measure on infinite d-regular tree is not unique). Joint work with Andreas Galanis, and Eric Vigoda.

**February 11, 2015, 12:30pm**

*Speaker*:**Martin Lackner, Vienna University of Technology**

*Topic*:**Recognizing Incomplete Single-Peaked and Single-Crossing Preferences**

*Abstract*: We consider the problem of deciding whether a given profile of incomplete votes (i.e., a profile of partial orders over a given set of alternatives) can be extended to a single-peaked or single-crossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding voters' preferences and we would like to understand whether the given preference profile has a specific structure, namely being single-peaked or single-crossing. In this talk, I will introduce these computational problems and related concepts. We will see that for incomplete votes the single-peaked and single-crossing restriction behave vastly different, both from a mathematical and algorithmic perspective.**February 25, 2015, 12:30pm**

*Speaker*:**Scott Ames, UR**

*Topic*:**On the Round Complexity of Precise Zero Knowledge**

*Abstract*: Precise zero knowledge introduced by Micali and Pass in (STOC06) guarantees that the view of any verifier V can be simulated in time closely related to the actual (as opposed to worst-case) time spent by V in the generated view. Informally, a zero-knowledge proof/argument is said to have a p (·,·)-precise simulator if the simulator uses at most p(n,t) steps to output a view in which V takes t steps. Micali and Pass show how to construct omega(logn)-round zero-knowledge proofs with constant-precision and omega(1)-round zero-knowledge proofs with polynomial-precision for all of NP. In this work, we provide optimal constructions for arbitrary precision. More precisely, we show that if L has an O(log(n)/log(g(n)))-round precise zero-knowledge argument with precision p(n,t) = c t g(n) + O(n c), then L in BPP. On the positive side, we show that for any L in NP there exists omega(log(n)/log(g(n)))-round precise zero-knowledge argument with precision p(·,·). For the specific case of constant precise zero-knowledge, we strengthen our lower bound to rule out simulators that achieve only constant probability deviation gap. We introduce a general framework to prove such lower bounds and prove each of our results in this framework.**March 11, 2015**(No meeting; UR Spring Break)**March 18, 2015, 12:30pm**(note: this talk is on a nonstandard parity Wednesday: an odd one)*Speaker*:**Henning Schnoor, University of Kiel, Germany**

*Topic*:**Noninterference with Local Policies**

*Abstract*: We develop a theory for state-based noninterference in a setting where different security policies---we call them local policies---apply in different parts of a given system. Our theory comprises appropriate security definitions, characterizations of these definitions, for instance in terms of unwindings, algorithms for analyzing the security of systems with local policies, and corresponding complexity results.**March 25, 2015**(No meeting; RIT Spring Break)**April 8, 2015, 12:30pm**

*Speaker*:**Chris Homan, RIT**

*Topic*:**Manipulation of Pairwise Voting Systems**

*Abstract*: An major trend in machine learning is to use increasingly sophisticated means obtain training data. For instance, rather than assign class labels to one item at a time, trainers may instead compare two or more items at once. Lee et al. show that under certain assumptions, one can approximate social choice functions through randomized elicitation of pairwise preferences. Manipulation is a real concern when such approaches are used in crowdsourced systems, where the trainers could rather easily conspire undetected to influence the outcome. We will use the framework of Lee et al. to formulate and consider the complexity of manipulation under elicitation of pairwise preferences.**April 22, 2015, 12:30pm**

*Speaker*:**Michael Wehar, UB**

*Topic*:**Intersection Non-Emptiness for Restricted Classes of Finite Automata**

*Abstract*: We consider the problem of deciding whether a finite list of regular languages has a non-empty intersection. That is, given a finite list of DFA's (deterministic finite automata), does there exist a string that satisfies all of the DFA's? This problem is in PSPACE rather than NP because the shortest satisfying string may have exponential length. In fact, this problem is PSPACE-complete. Many restrictions of this problem are hard as well. For example, if all the DFA's are shaped like trees with at most three final states, then the problem is NP-complete. The hardness follows because there is a reduction from 3-SAT where we represent each clause by a DFA that accepts if and only if the clause is satisfied.We will especially focus on the number of automata which we denote by k. We will investigate how the complexity of these problems grow with respect to the parameter k. For k DFA's, the problem is hard for non-deterministic klog(n) space. But, for k DFA's that are shaped like trees with at most three final states, the problem is solvable in deterministic O(log(n)) space where the coefficient of log(n) does not depend on k.

**Here are the talk lists for some previous years:**- 2013-2014
- 2012-2013
- 2011-2012
- 2010-2011
- 2009-2010
- 2008-2009
- 2007-2008
- 2006-2007
- 2005-2006
- 2004-2005
- 2003-2004
- 2002-2003
- 2001-2002
- 2000-2001

The seminar series is open to public, and is being 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).