Seminars in March 2014

  • Antoine Vigneron, A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space
    A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space
    Antoine Vigneron
    KAUST, Kingdom of Saudi Arabia
    2014/03/31 Monday 4PM-5PM
    Room 1409
    We show that the Gromov hyperbolicity of a discrete metric space at a fixed base-point cannot be computed in O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication algorithm than is currently known.
    Tags:

  • Frances A. Rosamond, Determining the Winner of a Dodgson Election is Hard
    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:

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

    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:

  • Seung jin Lee, Centrally symmetric polytopes with many faces
    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:

Monthly Archives