THEORY CANAL: The Rochester Theory Seminar Series 2011-2012 |
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 first and third Monday (and usually, when a fifth exists, the fifth Monday) of each month. (Due to slot demand, school holidays, and religious holidays, there are sometimes exceptions to that rule: Mondays of that form that we skip and Mondays not of that form that we don't skip. So see the schedule below for the actual dates.) The talks start at 12:30PM and typically take 60 minutes.
The meetings this year will be held in Room 70-3000 (the CS conference room; 3rd floor), Golisano College of Computing and Information Sciences, Rochester Institute of Technology, Rochester, NY 14623.
The meetings are open to the public; all are very welcome.
Chronological list of 12:30PM THEORY CANAL talks for the
2011-2012 academic year:
Speaker: Gahyun Park, SUNY Geneseo
Topic:
A Generalization of Multiple Choice Balls-into-Bins
In the multiple choice balls into bins problem, each ball is placed into the least loaded one out of $d$ bins chosen independently and uniformly at random ({\it i.u.r.}). It is known that the maximum load after $n$ balls are placed into $n$ bins is $\ln\ln n/\ln d + O(1)$.
In this paper, we consider a variation of the standard multiple choice processes. For $k < d$, we place $k$ balls at a time into $k$ least loaded bins among $d$ possible locations chosen {\it i.u.r.} We provide the maximum load in terms of $k$, $d$ and $n$. The maximum load in the standard multiple choice problem can be derived from our general formulation as a special case with $k=1$. More interestingly, our result indicates that, for any $d \leq (\ln n)^{\Theta(1)}$ and $k < d$, the maximum load is still $O(\ln\ln n)$. Our allocation scheme can be employed as optimal file replication and data partition policies in distributed file systems and databases. When a new file is created, $k$ copies/fragments of the file are stored into $k$ least loaded among $d$ randomly chosen servers, where $k$ is a tunable parameter that may depend on the level of load balance, file availability, fault tolerance, and popularity or size of a file.
Speaker: Andrew Lin
Topic:
SAT Solver Approaches to Problems in Voting
A weakness of all election systems of interest is the incentive, in some cases, for one or more voters to vote contrary to their true preferences. Significant work has been done on finding election systems in which the discovery of such an attack is provably hard. Earlier work has shown that while manipulation is NP-complete in the relatively simple election of weighted veto of three candidates, some known heuristics and algorithms for attacking the NP-complete problem of Partition can render this problem empirically easy in most cases, and that hard cases are exceedingly rare. However, a more recent result showed that applying the natural extensions of Partition and best-known algorithms of such did not yield similar results for more complex elections of more than three candidates. Partition also does not lend itself to solve other problems in election systems, such as bribery and control, or systems other than scoring protocols.
As much work has been performed on the solution to the Satisfiability (SAT) problem, we evaluate the encoding of the problems of interest into SAT instances, and the feasibility of solving these instances with the known algorithms for SAT. In doing so, we wish to investigate the inner workings of some known NP-complete manipulation problems, to evaluate whether or not they behave like the case of three candidates, in which hardness does not fall from being within the phase transition of the NP-complete problem, and if so, where the hard instances lie and their frequency.
We find that, using some known approaches to SAT in conjunction with some natural encodings of manipulation, all scoring protocols on a fixed number of candidates are potentially subject to the results of Walsh. In particular, we show empirically that hard-to-manipulate instances are exceedingly rare in this problem for all scoring protocols. We further show that some symmetry breaking is required to achieve this empirical result. We also evaluate an interesting case of a family of scoring protocols which is NP-hard to manipulate: that of unweighted Borda elections. We make an interesting discovery that, under the natural encoding of this problem, the empirical complexity of known approaches of SAT exhibit an unusual complexity behavior, with unsatisfiable problems and problems near the phase transition exhibiting lower search complexity. However, our results do not extend to other families of scoring protocols nor other problems such as bribery and control, at least under the best known algorithms for SAT on the natural encodings of these problems. We conjecture that a large candidate set may be the strongest defense against manipulation under the current understanding of NP-hardness.
Speaker: Daniel Stefankovic
Topic:
Hanani-Tutte theorem for x-monotone drawings
Hanani-Tutte theorem provides an algebraic characterization of planarity---a graph is planar if and only if it has a drawing in the plane in which every pair of (non-incident) edges intersects evenly. It is an interesting question whether this algebraic connection generalizes, for example, to restricted drawings or to the notion of crossing number.
We will consider the so-called x-monotone drawings (where edges are drawn in such a way that a vertical line intersects an edge at most once) and show that Hanani-Tutte theorem is true in this setting. Joint work with Radoslav Fulek, Michael Pelsmajer, and Marcus Schaefer.
Speaker: Qi Ge
Topic: Strong spatial mixing of $q$-colorings on Bethe lattices
We investigate the problem of strong spatial mixing of $q$-colorings on Bethe lattices.
By analyzing the sum-product algorithm we establish the strong spatial mixing of $q$-colorings on $(b+1)$-regular Bethe lattices, for $q \geq 1+\lceil 1.764b \rceil$. We also establish the strong spatial mixing of $q$-colorings on binary trees, for $q=4$.
This is a joint work with Daniel Stefankovic.
Speaker: Atri Rudra
Topic: List Decoding: The Master of Disguise
Suppose you want to communicate over a point-to-point noisy channel. If the noise is adversarial, then a classical observation due to Hamming states that one can only correct up to half the information- theoretically possible number of error if one wants to *uniquely* recover the transmitted information. However, if one is allowed to output a small list of possibilities, then one can indeed recover from information-theoretically optimal number of error. "List decoding" thus holds the promise of optimal communication even in the presence of *worst-case* errors. In its most obvious avatar, list decoding has applications in communication. On the other hand, theoretical computer scientists have found solutions to problems, which on the surface have nothing to do with communication but use list decoding under different guises. Most of these applications are in complexity theory.
This talk will first motivate list decoding and then give a quick tour of the progress on efficient list decoding algorithms in the past decade and a half. Then the talk will focus on two new (somewhat more practical but still somewhat surprising) applications of list decoding. In particular, we will see how list decoding can lead to sub- linear time algorithms for compressive sensing (which has applications in signal and image processing among others) and group testing (which has applications in biology among others). Finally, we will see how list decoding can prove that some existing hash functions are more powerful than previously thought, which leads to some applications in cloud security. The latter result also uses another staple of complexity theory-- Kolmogorov complexity.
The talk will be self-contained and is based on joint works with
Mohammad "Ifte" Husain (UB), Piotr Indyk (MIT), Steve Ko (UB), Hung
Ngo (UB), Ely Porat (Bar-Ilan), Ram Sridhar (UB) and Steve Uurtamo
(Groupon/UB).
Speaker: Rafael Pass
Topic: Constant-round Non-malleable Commitments from One-way Functions
Commitment schemes are one of the most fundamental cryptographic building blocks. Often described as the "digital" analogue of sealed envelopes, commitment schemes enable a sender to commit itself to a value while keeping it secret from the receiver. For many applications, however, the most basic security guarantees of commitments are not sufficient. For instance, the basic definition of commitments does not rule out an attack where an adversary, upon seeing a commitment to a specific value v, is able to commit to a related value (say, v - 1), even though it does not know the actual value of v. Non-malleable commitments, introduced by Dolev, Dwork and Naor in 1991, prevent against these types of attacks. In this work, we present the first constant-round non-malleable commitment based on the minimal assumption of one-way functions.
Joint work with Huijia Rachel Lin.
Speaker: David Kempe
Topic: Subset Selection for Linear Regression
One of the central problems in many data-driven sciences is the right selection of attributes to observe in order to accurately predict a variable of interest. Applications abound in areas as diverse as medical sciences (predicting medical conditions based on observable attributes), social sciences (predicting future behaviors or outcomes) and sensor networks, among others. In many of these cases, time or cost constraints prohibit sampling more than a few attributes. Also, many application domains use linear regression as a method of prediction, and evaluate the quality of attributes in terms of the R^2 fit with the quantity to be predicted. This motivates the following formal problem definition: "Given the covariances between observable variables X_i and a target variable Z, select k of the variables X_i such that the selected set has the best possible R^2 fit with Z."
The main result presented in this talk is that so long as the covariance matrix between the X_i variables is far from singular, greedy algorithms frequently used in practice are provably constant- factor approximations. The proof is based on extending the widely used concept of submodularity to a notion of approximate submodularity, and relating it to the spectrum of the covariance matrix. Furthermore, we will investigate various graph-theoretical properties of covariance matrices which allow for efficient exact or approximate algorithms.
We conclude with several exciting open questions.
[This talk is based on joint work with Abhimanyu Das, appearing in ICML 2011 and STOC 2008.]
Speaker: Andrew Reinders
Topic: Recognizing Numerical Sets Using Automata
Speaker: Robert Kleinberg
Topic: Improving Christofides' Algorithm for the s-t Path TSP
We present a polynomial-time approximation algorithm for the s-t path traveling salesman problem (TSP) in an arbitrary metric, whose approximation ratio is bounded above by 1.618..., the golden ratio. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints. Hoogeveen showed in 1991 that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree. We prove that this simple but crucial modification leads to an improved approximation ratio, surpassing the barrier set by the natural Christofides' algorithm variant. Our algorithm also proves that the integrality gap of the path-variant Held-Karp relaxation is bounded above by the golden ratio. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.
This is joint work with Hyung-Chan An and David Shmoys.
BIO: Robert Kleinberg is an Assistant Professor of Computer Science at Cornell University. His research studies the design and analysis of algorithms, and their applications to electronic commerce, networking, information retrieval, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies, where he assisted in designing the world's largest Internet Content Delivery Network. He is the recipient of a Microsoft Research New Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.
Speaker: Joel Seiferas
Topic: Approaches to Time- and Space-optimal String Matching
The string-matching problem is to find instances of a length-m pattern string in a longer length-n text string. The straightforward approach requires a pointer into each and worst-case time proportional to the product mn.
We will survey the evolution of improvements to this approach, ultimately to worst-case time that is linear in m and n, still using only a constant number of pointers into the strings. The ultimate algorithm can be implemented as a 6-head finite automaton.
Finally, we will focus on the key lemmas at the heart of such ultimate results.
Speaker: Alexander Lange
Topic: Ramsey Arrowing from Max-Cut
Given an undirected, loopless graph G, we write G --> (n_1,...,n_r)^e if for every r-coloring of the edges G, there is a monochromatic K_n in one of the colors. Let the edge Folkman number Fe(s,t;k) be the minimum number of vertices needed for a graph to arrow (s,t)^e but not contain K_k as a subgraph. Fe(3,3;4) is considered to be the ``most wanted'' of these numbers because it contains the smallest parameters for which the problem is open. In 2008, Dudek and Rödl showed that Fe(3,3;4) ≤ 941 using classical max-cut problem algorithms. We discuss their strategy, which uses computed eigenvalues to bound the maximum cut, and provide classic examples that show how it succeeds and fails. We conclude with plans of attacking Fe(3,3;4) using their method, which has already produced a smaller upper bound of 860, as well new strategies involving other max-cut approximation algorithms, such as the well-known Goemans-Williamson algorithm.
Speaker: Muthu Venkitasubramaniam
Topic: Towards Non-Black-Box Lower Bounds in Cryptography
We consider average-case strengthenings of the traditional assumption that coNP is not contained in AM. Under these assumptions, we rule out generic and potentially \emph{non-black-box} constructions of various cryptographic primitives (e.g., one-way permutations, collision-resistant hash-functions, constant-round statistically hiding commitments, and constant-round black-box zero-knowledge proofs for NP) from one-way functions, assuming the security reductions are \emph{black-box}.
Speaker: Curtis Menton
Topic: TBA
Speaker: TBA
Topic: TBA