4th workshop of the Center of Modern Computer Science
4. seminář Centra moderní informatiky
The fourth workshop of the Center of Modern Computer Science will take place on Wednesday December 4, 2013.
Centrum moderní informatiky zve na čtvrtý seminář. Přednášky juniorů centra se konají v průběhu programu ve středu 4. 12. 2013 v refektáři v budově MFF UK na Malé štraně.
| 9:30 - 10:20 | Rahul Santhanam: Algorithms for QBF Satisfiability, and Connections to Circuit Lower Bounds |
|---|---|
| 10:20 - 10:45 | coffee break |
| 10:45 - 11:15 | Neil Thapen: Parity games and propositional proofs |
| 11:15 - 11:45 | Petr Savicky: Boolean functions with a vertex-transitive group of automorphisms |
| 11:45 - 12:15 | Vit Jelinek: Splitting Permutation Classes |
| 12:15 - 14:00 | obed |
| 14:00 - 14:30 | Hans Raj Tiwary: Extended Formulations and Communication Protocols |
| 14:30 - 15:00 | Petr Gregor: Distance magic labelings of hypercubes |
| 15:00 - 15:30 | Tomas Kaiser: Colouring quadrangulations of projective spaces |
| 15:30 - 16:00 | Csanad Imreh: Online restricted assignment with migration |
Abstracts
Vit Jelinek: Splitting Permutation Classes
We say that a permutation p is `merged' from permutations q and r, if we can color the elements of p red and blue so that the red elements are order-isomorphic to q and the blue ones to r. With Claesson and Steingrímsson, we have shown, as a special case of more general results, that every permutation that avoids the subpermutation 1324 can be merged from a permutation that avoids 132 and a permutation that avoids 213. This is a simple example of a property called splittability: we say that a hereditary permutation class C is `splittable', if it has two proper hereditary subclasses A and B such that any element of C can be obtained by merging an element of A with an element of B.
In my talk, I will show how splittability helps in enumeration of restricted permutations, explain how splittability relates to other Ramsey-type properties, and point out a close connection between splittability of certain permutation classes and the notion of $\chi$-boundedness of circle graphs. I will then report on the recent progress in identifying which principal permutation classes are splittable.
Hans Raj Tiwary: Extended Formulations and Communication Protocols
A polytope $Q$ is called an extended formulation of polytope $P$ if $P$ is a projection of $Q$. In this talk I will discuss how extended formulations are related to communication protocols where two players Alice and Bob wish to compute some function exchanging as few bits as possible. I will discuss a theorem that shows that a small extended formulation is possible if and only if a communication protocol exists for computing the slack matrix of the polytope that requires small number of bits, and vice versa. I will then present examples of application of this theorem to show the existence of small extended formulations for certain polytopes.
Petr Gregor: Distance magic labelings of hypercubes
(Joint work with Petr Kovář.)
A bijective assignment of labels from 1 to n to the vertices of an n-vertex graph is called distance magic if the sum of labels on neighbors of each vertex is constant. This concept is motivated by magic squares and has applications in design of fair incomplete tournaments.
We show that the n-dimensional hypercube has a distance magic labeling for every n = 2 (mod 4). It is known that this condition is also necessary. This completes solution of a conjecture posed by Acharya et al. Moreover, we study additional magic properties of this labeling. In particular, we show that it is (in general) distance-d magic for every odd d.
