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.
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(n4) time for 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.