THEORY CANAL: The Rochester Theory Seminar Series 2015-2016 |
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.)
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).
Speaker: Tamalika Mukherjee, RIT-Math
Topic: Ring Learning With Errors: Homomorphic Encryption
Abstract: Homomorphic encryption is a method of performing calculations on encrypted data without decrypting them first. Fully Homomorphic Encryption (FHE) schemes can perform an arbitrary number of additions and multiplications but are practically inefficient to implement for industry standards. On the otherhand, Somewhat Homomorphic Encryption (SWHE) schemes can perform a limited number of multiplications on encrypted data and are much more efficient. We present one such SWHE scheme by Brakerski and Vaikuntanathan which uses the Ring Learning With Errors assumption. We will show our own implementation results and also introduce a mathematical aspect of the scheme that will serve as a basis for our future research.
Speaker: Zack Fitzsimmons, RIT
Topic: Voting with Ties
Abstract: Most of the computational study of election problems has assumed that each voter's preferences are, or should be extended to, a total order. However in practice voters may have preferences with ties. We study the complexity of manipulative actions on elections where voters can have ties, extending the definitions of the election systems (when necessary) to handle voters with ties. We show that for natural election systems allowing ties can both increase and decrease the complexity of manipulation and bribery, and we state a general result on the effect of voters with ties on the complexity of control.
This is joint work with Edith Hemaspaandra.
Speaker: Rupam Acharyya, UR
Topic: Counting Popular Matchings
Abstract: We study the problem of counting the number of popular matchings in a given instance. A popular matching instance consists of agents A and houses H, where each agent ranks a subset of houses according to their preferences. A matching is an assignment of agents to houses. A matching M is more popular than matching M' if the number of agents that prefer M to M' is more than the number of people that prefer M' to M. A matching M is called popular if there exists no matching more popular than M. McDermid and Irving gave a poly-time algorithm for counting the number of popular matchings when the preference lists are strictly ordered. We first consider the case of ties in preference lists. Nasre proved that the problem of counting the number of popular matching is #P-hard when there are ties. We give an FPRAS for this problem. We then consider the popular matching problem where preference lists are strictly ordered but each house has a capacity associated with it. We give a switching graph characterization of popular matchings in this case. Such characterizations were studied earlier for the case of strictly ordered preference lists (McDermid and Irving) and for preference lists with ties (Nasre). We use our characterization to prove that counting popular matchings in capacitated case is #P-hard.
Speaker: Adam Scrivener, UR
Topic:
On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography
Abstract: Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2014) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors.
We continue this line of work to establish the following results:
This is joint work with Doug Miller, Jesse Stern, and Muthuramakrishnan Venkitasubramaniam
Speaker: Nicholas Chusid, RIT
Topic:
Counting (s,t)-cuts in 8-connected grid graphs
Abstract: We present several algorithms and optimizations that utilize a planar graph structure to quickly count the number of minimum (s,t)-cuts. A focus is placed on the application of these algorithms to computer vision. The 8-connected grid is a graph that appears in these applications, yet fast (s,t)-cut counting algorithms were previously unknown. While the problem of counting minimum (s,t)-cuts is #P-complete for general graphs, previous work designed polynomial-time algorithms for several graph classes such as planar graphs (Bezakova-Friedlander) and graphs of bounded genus (Chambers-Fox-Nayyeri). We present polynomial-time algorithms for the 8-connected grid for certain settings of edge weights.
This is joint work with Ivona Bezáková and Rachel Silva.
Speaker: Hammurabi Mendes, UR
Topic:
Multidimensional $\epsilon$-Approximate Agreement and Computability in Byzantine Systems
Abstract: This talk is divided in two parts. The first part presents the multidimensional $\epsilon$-approximate agreement problem, defined as follows. Consider a distributed system with asynchronous communication and Byzantine failures (that is, arbitrary, even malicious failures). Each process inputs a value in $\mathbb{R}^d$ with $d \ge 1$, and all non-faulty (i.e., non-Byzantine) processes must finish with values also in $\mathbb{R}^d$ where: (1) outputs lie within a distance $\epsilon$ of each other; and (2) outputs are in the convex hull of non-faulty process inputs only. This problem generalizes the traditional $\epsilon$-approximate agreement of the 1980's, and has implications to computability for more general Byzantine asynchronous tasks.
The second part discusses how to generally characterize computability in Byzantine, asynchronous systems with tools adapted from combinatorial topology. Tasks are formalized with a pair of combinatorial structures called simplicial complexes, one for process inputs (the input complex), and another for process outputs (the output complex). A map between the input complex and the output complex defines task semantics. In the talk, we see how a Byzantine asynchronous task is solvable if and only if a "dual" asynchronous, crash-failure task is solvable as well. We are then able to characterize computability for Byzantine asynchronous tasks with a concise, topology-based language.
Speaker: Joel Seiferas, UR
Topic: What makes on-line multiplication difficult?
Abstract: We revisit the Cook-Aanderaa and Paterson-Fischer-Meyer superlinear time lower bounds for on-line multiplication, and especially the STOC-sketched Kolmogorov-complexity-based simplification by Reisch and Schnitger.
Speaker: Andrew Hughes, UB
Topic: Disjoint NP-Pairs, Proof Systems, and NP Listability
Abstract: This talk will survey some of the results relating disjoint NP-pairs, proof systems for languages, and the NP listability of languages.
A disjoint NP pair is a pair of non-empty languages in NP that are disjoint. A proof system for a language L is a function f: $\Sigma^*$ -> L that is onto. A language is NP listable, denoted List(L,NP,NP), if there exists a computable enumeration of NP machines that accept all subsets of L belonging to NP.
Though seemingly different, these definitions are closely related. Under certain conditions they can be equivalent notions. From this, there are interesting structural results we will explore as well as some questions that naturally arise from them.
Speaker: Muthuramakrishnan Venkitasubramaniam, UR
Topic:
Secure Computation from Millionaires
Abstract: The standard method for designing a secure computation protocol for function f first transforms f into either a circuit or a RAM program and then applies a generic secure computation protocol that either handles boolean gates or translates the RAM program into oblivious RAM instructions respectively.
In this work, we show a large class of functions for which a different algorithmic approach to secure computation results in more efficient protocols. The first such examples of this technique was presented by Aggrawal, Mishra, and Pinkas (J. of Cryptology, 2010) for computing the median; later, Brickell and Shmatikov (Asiacrypt 2005) showed a similar technique for minimum spanning tree and a variant of shortest paths.
We generalize the technique in both of those works and show that it applies for a large class of problems including matroid optimizations, sub-modular optimization, convex hulls, and other scheduling problems. The crux of our technique is to securely reduce these problems to secure comparison operations. We then describe general properties under which simulation-based security can be achieved for honest-but-curious and covert adversary models.
Joint work with abhi shelat (U. of Virginia).
Speaker: David Narvaez, RIT
Topic:
Structural Analysis of the SAT Formulation of Graph Edge-Coloring and k-Majority Problems
Abstract: We are interested in solving combinatorial problems, i.e., problems whose domain is a discrete mathematical structure (e.g. a graph, or a set). These problems have numerous applications in virtually every aspect of modern computing and are, in general, computationally difficult because of the numerous cases that need to be inspected. One popular strategy to solve these problems is to encode them as Boolean formulas whose constraints model the constraints of the original problem domain. This is done in order to exploit the wide variety of Boolean satisfiability solvers currently available that seem to perform well in many problem instances. Unfortunately, many deceivingly simple combinatorial problems of an abstract nature do not seem to benefit from these advances, and their solution is still unknown. This research analyzes the structure of Boolean formulas that encode two problems of combinatorial nature: the graph edge-coloring problem and the k-majority graph problem. The main purpose of this analysis is to understand how much of the recent advances in SAT solvers can be applied to these problems.