2nd Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)
The meeting takes place on Wednesday December 4, 2013. All lectures are at the "Refektář", 1st floor, in the building of MFF UK in Malá Strana, Malostranské nám. 5.Program
| 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
Rahul Santhanam: Algorithms for QBF Satisfiability, and Connections to Circuit Lower Bounds
(joint work with Ryan Williams)
We give the first non-trivial algorithms for satisfiability of polynomial-size quantified CNFs. We show that satisfiability of polynomial-size quantified CNFs with q alternations can be solved by zero-error probabilistic algorithms in time 2^{n-n^{1/(q+1)}}. This gives a non-trivial improvement over brute-force search when q=o(log(n)/loglog(n)). For q=\omega(log(n)), we observe that non-trivial savings can be achieved by a simple game tree search algorithm with running time 2^{n-\Omega(q)}.
We investigate the question of whether our algorithmic results can be improved, and show that such improvements would lead to new circuit lower bounds. Specifically, a satisfiability algorithm for poly-size quantified CNFs running in time 2^{n-n^{\omega(1/q)}} would imply NEXP does not have polynomial-size formulas. Similarly, a satisfiability algorithm for poly-size quantified CNFs running in time 2^{n-\omega(log(n))} would imply NEXP does not have polynomial-size formulas.
Neil Thapen: Parity games and propositional proofs
Parity games are two-player games about moving a token around a finite graph, with applications in automata theory, logic and verification. The decision problem for such games is to decide which player has a winning strategy. It is unknown whether this problem is in P, and this has been the subject of intensive research. A propositional proof system is weakly automatizable if there is a polynomial time algorithm which separates satisfiable formulas from formulas which have a short refutation in the system. We show that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time. Resolution is a well-studied propositional proof system, which in particular can be used to model the workings of most modern SAT solving algorithms.
Petr Savicky: Boolean functions with a vertex-transitive group of automorphisms
A Boolean function is called vertex-transitive (or transitive for simplicity), if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the cube. Several constructions of transitive functions and some of their properties will be presented.
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.
Tomas Kaiser: Colouring quadrangulations of projective spaces
By a well-known result of Youngs, every quadrangulation of the projective plane has chromatic number either 2 or 4. We extend the definition of a quadrangulation to higher dimensions and show that every non-bipartite quadrangulation of the projective n-space has chromatic number at least n+2. We also discuss relations between projective quadrangulations and the classes of Mycielski and Kneser graphs. The talk is based on joint work with Matěj Stehlík.
Csanad Imreh: Online restricted assignment with migration
(joint work with Matthias Hellwig)
In on-line optimization, an algorithm must make its decisions based only on past events without any solid information about future data. Such algorithms are called online algorithms. Since an online algorithm makes its decisions based only on partial information, without knowing the whole instance in advance, we cannot expect it to give the optimal solution that can be produced by an algorithm that has all the necessary information. An algorithm that knows the whole input in advance is called an offline algorithm. Usually we use a worst-case analysis approach called competitive analysis to measure the efficiency of the online algorithms. This means that we compare the objective function value of the solution produced by the on-line algorithm with the optimal offline objective function value. With online minimization problems, an online algorithm is called $C$-competitive if the cost of the solution created by the algorithm is at most $C$ times more than the optimal offline cost for each input. The competitive ratio of an algorithm is the smallest $C$ for which the algorithm is $C$-competitive.
In makespan scheduling problems, jobs are characterised by their processing times and one has to assign them to machines, and the goal is to minimize the maximal completion time. In the restricted assignment scheduling model each job has some processing time and also a subset of the machines is assigned to a job. The jobs are only allowed to be scheduled on the machines assigned to them. In this model no online algorithm can have better competitive ratio than $\log(m)$ where $m$ is the number of machines. This lower bound is also true if each job has unit size.
We will present a semi-online version of the restricted assignment scheduling problem, where some migration is available among the jobs after the arrival of a new job. This semi-online relaxation (where some jobs are allowed to change its machine) usually makes the problem easier in the sense that the competitive ratios of some optimal algorithms are smaller than what can be achieved in the pure online model. It was already known that if we allow to reschedule $O(\log(m))$ job after the arrival of each job then we can achieve a constant competitive algorithm in the case of unit sized jobs. We consider the general case and present an algorithm for arbitrary sized jobs which is $o(\log(m)$-competitive if $o(\log(m)$ times the total load of the arrived jobs can be rescheduled.
