Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Frances A. Rosamond, Determining the Winner of a Dodgson Election is Hard

Tuesday, February 25th, 2014
Determining the Winner of a Dodgson Election is Hard
Frances A. Rosamond
Charles Darwin University, Australia
2014/03/25 Tuesday 4PM -5PM
Room 1409
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

(CS Colloquium) Michael R. Fellows, The Evolution of the Multivariate Revolution in Algorithmics

Tuesday, February 25th, 2014

FYI (CS Colloquium)

The Evolution of the Multivariate Revolution
in Algorithmics
Michael R. Fellows
Charles Darwin University, Australia
2014/03/24 Monday 4PM – 5:30PM
E3-1 CS Bldg. Room 1501
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Seung jin Lee, Centrally symmetric polytopes with many faces

Monday, February 24th, 2014
Centrally symmetric polytopes with many faces
Seung jin Lee
KIAS, Seoul
2014/03/17 Monday 4PM-5PM
Room 1409
We study the convex hull of the symmetric moment curve Uk(t)=(cost, sint, cos3t, sin3t, …., cos(2k-1)t, sin(2k-1)t) in R2k 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 t1, …, tk lie in an arc of a certain length φk > π/2, the points Ut1, …, Utk span a face of the convex hull of Uk(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 3d/2 vertices. This is joint work with Alexander Barvinok and Isabella Novik.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Boris Aronov, The complexity of unions of shapes

Wednesday, December 18th, 2013
The complexity of unions of shapes
Boris Aronov
Department of Computer Science and Engineering
Polytechnic Institute of NYU
2013/12/20 Friday 4PM-5PM
Room 1409
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).

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.

Tags:
Posted in 2013, KAIST Discrete Math Seminar | Comments Closed

Eunjung Kim (김은정), On subexponential and FPT-time inapproximability

Monday, November 18th, 2013
On subexponential and FPT-time inapproximability
Eunjung Kim
CNRS, LAMSADE, Paris, France
2013/12/18 Wednesday 4PM-5PM
Room 1409

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.

Tags:
Posted in 2013, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »