KAIST Discrete Math Seminar

Computational social choice is a growing discipline at the interface of social choice theory and computer science. It is concerned with the application of computational techniques to the study of social choice mechanisms, and with the integration of social choice paradigms into computing. Several problems have been investigated in the framework of parameterized complexity. This talk will describe the election scheme of Charles Dodgson. In 1876 the mathematician Charles Dodgson (better known as Lewis Carroll) formulated a rule that defines the winner of an election even if there is no Condorcet winner. A candidate who beats every other candidate in pairwise comparison is said to be a Condorcet winner. Unfortunately, an election may have a cyclic structure (candidate a beats b, candidate b beats c and c beats a), and therefore no candidate who beats all others in pairwise comparison. The Dodgson Score measures how close a candidate is to being a Condorcet winner. Candidates with a minimum Dodgson Score are the election winners. As are many election methods, Dodgson Score is NP-hard. This talk discusses the complexity of Dodgson Score in the parameterized framework. We give a reduction from Multi-Colored Clique to show that Dodgson Score, parameterized by the number of votes, is W[1]-hard. When parameterized by the number of swaps, Dodgson Score is FPT, but we show by polynomial parameter transformation that it has no polynomial kernel.

There has been underway for some decades, with considerable practical consequences, a multivariate revolution in the design of algorithms and the assessment of computational complexity. Parameterized complexity has brought this shift into focus, naming the issues, and offering a multivariate mathematical framework for the central questions that confront the challenge of designing effective algorithms for intrinsically difficult computational problems. Iinternally to this new scientific direction of the central enabling scientific discipline of our time: algorithmics — who lacks a new flood of data? — is a story about how this multivariate revolution has evolved and is still unfolding. The talk will tell the story, in an entertaining way, accessible to students in any field of science that computing serves.

We study the convex hull of the symmetric moment curve U_k(t)=(cost, sint, cos3t, sin3t, …., cos(2k-1)t, sin(2k-1)t) in R^2k and provide deterministic constructions of centrally symmetric polytopes with a record high number faces. In particular, we prove the local neighborliness of the symmetric moment curve, meaning that as long as k distinct points t₁, …, t_k lie in an arc of a certain length φ_k > π/2, the points U_t1, …, U_tk span a face of the convex hull of U_k(t). In this talk, I will use the local neighborliness of the symmetric moment curve to construct d-dimensional centrally symmetric 2-neighborly polytopes with approximately 3^d/2 vertices. This is joint work with Alexander Barvinok and Isabella Novik.

Over the years, the following class of problems has been studied quite a lot: Given a class of simply-shaped objects in the plane (disks, unit disks, squares, axis-aligned squares, isosceles triangles, shapes definable with a small number of polynomial equations and inequalities), how complicated can be the union of N shapes from the class? There are several different ways in which one can measure this (combinatorial) complexity. Two popular measures are the number of connected components of the complement, and the number of places where two object boundaries intersect on the boundary of the union (so-called “vertices” of the union).</p>

It is easy to see that, if each object is “simple,” the union of N objects cannot be larger than O(N^2) and a matching construction is easy. Are there classes of objects for which this quantity is near-linear in N? (Yes, there are: disks, axis-aligned squares, and more.) The quest for such classes, over the years, motivation for the problem, generalizations to higher dimensions, and other puzzles will constitute the content of this talk.

If I ever get to it, the latest and most amazing result in this area is joint work with Mark de Berg, Esther Ezra, and Micha Sharir. It is quite technical and I will not be able to say much about this during the talk, but if anyone is interested, I can provide lots of technical details on request. An overview of the subject will be mostly based on a survey of Agarwal, Pach, and Sharir.

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, several independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0<r<1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts and techniques used to obtain such results.