THEORY CANAL: The Rochester Theory Seminar Series 2009-2010 |
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 to 75 minutes.
The meetings for the rest of this semester will be held in Room 601, Computer Studies Building, University of Rochester, Rochester, NY 14627.
The meetings are open to the public; all are very welcome.
Chronological list of 12:30PM THEORY CANAL talks for the
2009-2010 academic year:
Speaker: Piotr Faliszewski, AGH University Krakow
Topic: Multimode Control Attacks on Elections
In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.
This talk is based on joint work with Edith Hemaspaandra and Lane A. Hemaspaandra.
Speaker: Daniel Stefankovic, UR
Topic: Crossing numbers
Crossing numbers of graphs are important, yet inadequately understood. To learn more about the concept diverse variants (geometric, topological, and algebraic) were proposed by Mohar, Pach, Toth, and Tutte. I will describe the known connections as well as some new results (joint work with Marcus Schaefer and Michael Pelsmajer).
Speaker: Qi Ge, UR
Topic: On approximately counting independent sets in bipartite graphs
Counting independent sets is proved to be #P-hard even in planar bipartite graphs, however whether there is a fully polynomial randomized approximation scheme remains open. In this work, we investigate the problem of approximately counting independent sets in bipartite graphs. This is a joint work with Daniel Stefankovic.
Speaker: Mark Wilson, University of Auckland
Topic: Manipulability of voting rules
Almost every voting rule can be manipulated by an insincere voter. Much research has been undertaken to try to minimize the occurrence of such manipulation (for example, by making use of computational complexity) and to compare manipulability of various rules. I discuss recent work in measuring how manipulable a given rule is, argue that much of the recent literature has been generated by misguided assumptions, and say what I think we ought to be studying.
Speaker: Curtis Menton, RIT
Topic: Range Voting is Resistant to Control
Social choice theory is concerned with developing and evaluating voting systems, both for the use of political and organizational elections and for use as decision making process for multiagent systems. Particularly in the context of multiagent systems, computational resistance to various types of control has become a desired property of a voting system. Though manipulative actions may always be possible, strong computational barriers to efficient control can give us sufficient confidence in the integrity of an election.
Range Voting is a natural extension of approval voting that is resistant to a large number of cases of control. In particular, the variant Normalized Range Voting has the largest number of control resistances among natural voting systems.
Speaker: Stanislaw Radziszowski, RIT
Topic: Some Ramsey Problems - Computational Approach
Ramsey Theory studies the conditions of when a combinatorial object necessarily contains some smaller given objects. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey Theory. In the case of graph Ramsey numbers one studies partitions (colorings) of the edges of the complete graph, under the condition that each of the parts (colors) avoids some prespecified graph. In this talk we will overview the main known results about Ramsey numbers for which triangles are avoided in at least one of the colors. The currently smallest open cases involving triangle are the classical Ramsey numbers R(3,10), R(3,3,4) and R(3,3,3,3). We will also present recent progress on the famous open Ramsey-type triangle-avoiding problem: What is the smallest K4-free graph, for which any edge 2-coloring must contain at least one monochromatic triangle? Most of the discussed results were obtained with the help of computer algorithms.
Speaker: Ivona Bezakova, RIT
Topic: On the Diaconis-Gangolli Markov Chain for Sampling
Contingency Tables with Cell-Bounded Entries
The problems of uniformly sampling and approximately counting contingency tables have been widely studied, but efficient solutions are only known in special cases. One appealing approach is the Diaconis and Gangolli Markov chain which updates the entries of a random 2x2 submatrix. This chain is known to be rapidly mixing for cell-bounded tables only when the cell bounds are all 1 and the row and column sums are regular. We demonstrate that the chain can require exponential time to mix in the cell-bounded case, even if we restrict to instances for which the state space is connected. Moreover, we show the chain can be slowly mixing even if we restrict to natural classes of problem instances, including regular instances with cell bounds of either 0 or 1 everywhere, and dense instances where at least a linear number of cells in each row or column have non-zero cell-bounds.
This is joint work with Nayantara Bhatnagar and Dana Randall.
Speaker: Linji Yang, Georgia Tech
Topic: Phase Transition for the mixing time of the Glauber
Dynamics for coloring regular trees
We prove that the mixing time of the Glauber dynamics for random $k$-colorings of the complete tree with branching factor $b$ undergoes a phase transition at $k=b(1+o_b(1))/\ln{b}$. Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with $n$ vertices for $k=Cb/\ln{b}$ colors with constant $C$. For $C\geq 1$ we prove the mixing time is $O(n^{1+o_b(1)}\ln^2{n})$. On the other side, for $C< 1$ the mixing time experiences a slowing down, in particular, we prove it is $O(n^{1/C + o_b(1)}\ln^2{n})$ and $\Omega(n^{1/C-o_b(1)})$. The critical point $C=1$ is interesting since it coincides (at least up to first order) to the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.
Speaker: Xi Chen, University of Southern California
Topic: From Games to Markets: On the Computation of
Equilibria
In the past decade, models and approaches from Game Theory and Economics have been widely applied in the study of large-scale competitive environments such as the Internet and e-commerce. The concept of equilibria, i.e., that of stable states, serves as one of the key tools in such studies, and its computation has attracted great attention. In this talk, we will focus on the problem of computing equilibria in two of the most fundamental models of competitions in Game Theory and Economics: games and markets. Both problems have a long intellectual history. In 1950, Nash showed that every game has an equilibrium. In 1954, Arrow and Debreu showed that under very mild conditions, every market has an equilibrium. While games and Nash equilibria are used to predict the behavior of selfish agents in conflicting situations, the study of markets and market equilibria laid down the foundation of competitive pricing. Other than the fact that both existence proofs heavily rely on fixed point theorems, the two models look very different from each other. In this talk, we will review the recent characterizations of how difficult it is to compute or to approximate Nash equilibria in two-player games. We will then show that these results also significantly advanced our understanding about equilibria in the market setting. No prior knowledge of Game Theory will be assumed for this talk.
Speaker: Satyaki Mahalanabi, UR
Topic: Active learning of Halfspaces
I will survey algorithms for learning homogenous halfspaces under the uniform distribution on the unit $d$-dimensional sphere S^{d-1}. I will focus on the active learning setting, in which the learning algorithm can choose which samples it wants labelled. The goal is to design an efficient algorithm which improves on the sample complexity in the supervised setting. While such algorithms exist in the PAC learning model, it is an open question whether there are such algorithms in the more challenging agnostic learning model.
Speaker: Wolfgang Bein, University of Nevada, Las Vegas
Topic: Knowledge States: A Tool in Randomized Online
Algorithms
We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms.The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory. We give new results for the two server problem and the paging problem. We present a knowledge state algorithm for the two server problem over Cross Polytope Spaces with a competitive ratio of 19/12, and show that it is optimal against the oblivious adversary. Regarding the paging problem, Borodin and El-Yaniv had listed as an open question whether there exists an H_k-competitive randomized algorithm which requires O(k) memory for k-paging. We have answered this question in the affirmative using knowledge state techniques.