Theoretical Computer Science

Prof. Paweł Idziak

Wednesday 16:15 - 18:00, room 0174

This is our main seminar. We study problems in graph theory, partial ordered sets, online algorithms, computational complexity. This is also the place where we present our most recent results.

Previous seminars

Nobu-Yuki Suzuki,Shizuoka University, Japan
Epistemic logic and game theory
A brief overview of epistemic logics and their game-theoretical applications is given. This interdisciplinary field has many aspects arising from various research lines. In this talk, I give an outline of the recent developments of epistemic-logical approach to decision making process in game-theoretical situations.  
Grzegorz Łukasik
Mobile Robots Contests
Mobile Robots Contests organized by Computer Science and Technology University is presented: rules of the contest, the problems that students were solving and intresting solutions that were implemented. The first three places were taken by teams from Jagiellonian University.  
Contest home page:
Michael Sołtys,McMaster University,Hamilton, ON, Canada
P vs NP
The "P vs NP" problem is a central problem of theoretical computer science, and indeed of mathematics (it was named one of the seven Millennium Problem by the Clay Mathematical Institute, and there is a one million dollar prize for a solution: Despite thirty years of intense efforts, we are not near a solution, and we do not have promising techniques to tackle this problem. For example, since diagonal arguments "relativize", they will probably not work in this case. Exponential lower bounds on Boolean circuits are also hopelessly difficult to obtain. De-randomizing turns out to be just as difficult as separating P and NP. Cook proposed an attack based on a program of finding lower bounds for stronger and stronger propositional proof systems, building a repertoire of techniques and lower bounds, and ultimately showing that no polynomially bounded propositional proof system exists. The consequence of that would be that NP is not equal to coNP, and thus P is not equal to NP. In this talk, I will concentrate on this line of attack.  
11.05.2005,Lech Palmowski
Seventeen lines and one-hundred-and-one points
A curious problem from additive number theory is investigated: Given two positive integers S, Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?  
G. J. Woeginger, Seventeen lines and one-hundred-and-one points, Theoretical Computer Science 321 (2004), 415-421
Grzegorz Gutowski
Computational aspects of the 2-dimension of partially ordered sets

A well-known method to represent a partially ordered set consists in associating to each element of P a subset of a fixed set S={1,..,k} such that the order relation coincides with subset inclusion. Given an order P, minimizing the size of the encoding, i.e. the cardinal of S, is however a difficult problem. The smallest size is called the 2-dimension of P. The paper details a proof that computing 2-dimension of a given poset is NPC. Reduction allows to prove the non-approximability of the problem. Later on the complexity of the 2-dimension for the class of trees is investigated. Authors present a 4-approximation algorithm for this class.  
M. Habibb, L. Nourinea, O. Raynauda and E. Thierry, Computational aspects of the 2-dimension of partially ordered sets, Theoretical Computer Science 312 (2004), 401-431

Grzegorz Herman
The Complexity of Random Ordered Structure

One of the ways of expressing the complexity of a structure is the minimal "depth" of quantifiers in a formula that describes it. The presented paper discusses such complexity of two types of structures. The authors prove that the complexity of a random bit string is O(loglogn), with high probability, and the complexity of an ordered random graph - Theta(log*n), with high probability.  
J.H. Spencer, K.St.John , The Complexity of Random Ordered Structure

Mikołaj Zalewski
On-line Ramsey Theory
The Ramsey game is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monchromatic copy of a fixed target graph H, keeping the constructed graph in a prescribed class G. The main problem is to recognize the winner for a given pair H, G. In particular, authors of paper prove that Builder has a winning strategy for any k-colorable graph H in the game played on k-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. They show that the class of outerplanar graphs does not have this proberty. The question of whether planar graphs are self-unaviodable is left open.  
J.A. Grytczuk, M. Haluszczak, H.A.Kierstead, On-line Ramsey Theory, The Elektronic Journal of Combinatorics 11(1), 2004
Wiktor Żelazny
Online Algorithms for Market Clearing
Randomized on-line algorithms that maximalize profit and liquidity of marketplace are presented. They work by finding a maximal set with perfect matching in subgraph of bid history graph - before incoming intervals are applied, some of them (or some of graph edges from incoming vertices) are removed, based at random criteria. Proof that estimated profit produced by optimal algorithm cannot be greater then estimated profit of presented algorithm was also shown.  
A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002)
Wiktor Żelazny
Online Algorithms for Market Clearing
This talk presents an online algorithm able to find maximal set W of vertexes of n-interval graph, such that a perfect matching exists on W. The alghoritm works on interval representation of graph and new intervals must be introduced in legal way (described in previous talk) for it to work, but it's competitive ratio is equal 1. Proof of alghoritm's optimality was presented.  
A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002)
Jacek Krzaczkowski
Counting solutions of equations over two-element algebras.
I refered my results connected with counting solutions of equations and systems of equations over fixed two-element algebra. It came out that the computational complexity of these problems depends only on termal clone of the algebra. I presented the classification of the computational complexity of the problems mentioned above.  
Wiktor Żelazny
Online Algorithms for Market Clearing
A n-interval graph is created from interval graph by painting it's vertexes with n colours and removing all edges between vertices of the same colour. This talk introduced n-interval graphs, as well as the way their interval representation can represent history of buy and sell bids on exchange auction. Objectives of maximalizing marketplace's profit and liquidity are formulated as online problems, as new intervals are being introduced every time a new bid appears. A way of legal introduction of new intervals, corresponding to apperance of new bids, is described.  
A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscipt (2002)
Grzegorz Gronkowski
A boolean function requiring 3n network size.
First part of talk contains a simple proof, that there exist functions with a nonlinear lower bound for the network complexity. The proof is based on a counting method. Afterwards I present Norbert Bloom's result, who defined n-ary boolean function with a 3n lower bound. The proof shows, that 3n-3 is a minimal number of logic gates which is necessary for computing this function.  
Norbert Bloom, A boolean function requiring 3n network size.
T. Krawczyk,E. Szczypka
Comparability graphs.
A graph G=(V,E) is a comparability graph if there exists a partial order (V,<) such that there exists an edge between vertices v and w iff either v < w or w < v. In our talk we presented a polynomial time algorithm (the best known that solves a similar problem - Spinrad, McConnell - has a complexity O(n+m)) for deciding whether a given graph G=(V,E) is a comparability graph. In our method we investigated relations that exist between sets of neighborhoods in comparability graphs.  
Marek Kwiatkowski
Dr. Frankenstein's Approach to On-line Algorithms
Let A1...An be on-line algorithms for a problem P, competitive over subsets I1...In of inputs respectively. In this talk we show that under certain assumptions on P and I1...In it is possible to give an on-line algorithm for P that is competitive over all possible inputs. Two solutions are given: for deterministic and randomized algorithms.  
Yossi Azar, Andrei Z. Broder, Mark S. Manasse "Dr. Frankenstein's Approach to On-line Algorithms" (extended abstract)
Krzysztof Maczyński
P-time algorithm for tree decomposition
In my talk I presented a polynomial time algorithm for deciding whether a given tree is arbitrarily vertex decomposable (AVD) in a limited sense concerning no more than a constant number of components and if so, constructing one of possibly exponentially many such decompositions. I also assumed a constant bound on the maximal degree of the tree but this condition was shown to be unnecessary by a slight modification to my algorithm proposed by Mikołaj Zalewski. Additionally I detailed a construction of a maximally long greedy sequence over a set of colours whose cardinality is given. I characterized all sequences of equal length, proved that no longer ones exist and explicited a cubic function computing the length from the number of colours allowed.  
Jan Jeżabek
Graphs with high girth and high chromatic number
This talk introduces a basic tool of the probabilistic method - the first moment method. The method is illustrated with an application to satisfiability problems. A simple theorem is presented stating that any instance of k-SAT with fewer than 2^k clauses is satisfiable. The first moment method is then used to prove that for every g, k >= 1 there exist graphs with no cycles of size g and with chromatic number greater than k.  
M.Molloy, The Probabilistic Method, in: M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic Methods for Algorithmic Discrete Mathematics, Springer 1998
Piotr Micek
Natural algorithm for Online Chain Covering of Upgrowing Interval Posets
We have already proven that a competitive ratio for Online Chain Covering of Upgrowing Posets is equal to 2. At this talk I present a simple online algorithm which has optimal competitive ratio.  
Bartłomiej Bosek
Lowerbound for Online Chain Partitioning of Upgrowing Interval Posets

Bartek presents that there is no online algorithm for chain covering problem of upgrowing posets using less than 2w-1 chains to cover a width w poset.  

Paweł Walter
Online Bin Packing with two item sizes

In the well-studied on-line bin packing problem (BPP) we are given a set of items and a sequence of their sizes and are required to pack them into a minimum number of unit-capacity bins. The problem of finding the competitive ratio in the general case is open. In the analysed paper BPP is considered restricted to the case of two distinct item sizes. My talk based on this paper consists of an algorithm solving this particular case at an asymptotic competetive ratio of 4/3 and a proof that 4/3 is also here a valid lower bound.  
G.Gutin, T.Jensen, A.Yeo, Optimal on-line bin packing with two item sizes, manuscript (2004)

Tomek Krawczyk
NP-completeness of posets embedding into boolean lattice
Let p < q and p,q from N. A bipartitie graph G=(X \cup Y,E) embeds into a lattice of subsets on levels p and q if there exist n from N, injections f: X --> {n \choose p}, g: Y--> {n \choose q} such that there is an edge between x from X and y from Y iff f(x) < g(y). In my talk I proved that the problem of deciding whether a given bipartite graph G=(X \cup Y,E) embeds into lattice of subsets on levels p and q is NP-complete if p>1 and is in P if p=1.  
Piotr Micek
Open Problems from Workshop on On-Line Algorithms 2004
  • 1
  • 2