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.
|
01.07.2005 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. |
|
01.06.2005 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. References:Contest home page: http://www.best.agh.edu.pl/konkurs/ |
|
18.05.2005 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: http://www.claymath.org/millennium). 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. |
|
16.05.2005 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? References:G. J. Woeginger, Seventeen lines and one-hundred-and-one points, Theoretical Computer Science 321 (2004), 415-421 |
|
04.05.2005 27.04.2005 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. |
|
20.04.2005 30.03.2005 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. |
|
23.03.2005 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. References:J.A. Grytczuk, M. Haluszczak, H.A.Kierstead, On-line Ramsey Theory, The Elektronic Journal of Combinatorics 11(1), 2004 |
|
09.03.2005 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. References:A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002) |
|
01.03.2005 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. References:A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002) |
|
23.02.2005 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. |
|
26.01.2005 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. References:A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscipt (2002) |
|
12.01.2005 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. References:Norbert Bloom, A boolean function requiring 3n network size. |
|
05.01.2005 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. |
|
15.12.2004 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. References:Yossi Azar, Andrei Z. Broder, Mark S. Manasse "Dr. Frankenstein's Approach to On-line Algorithms" (extended abstract) |
|
08.12.2004 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. |
|
01.12.2004 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. References:M.Molloy, The Probabilistic Method, in: M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic Methods for Algorithmic Discrete Mathematics, Springer 1998 |
|
24.11.2004 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. |
|
17.11.2004 10.11.2004 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. |
|
03.11.2004 27.10.2004 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. |
|
13.10.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. |
|
06.10.2004 Piotr Micek |
Open Problems from Workshop on On-Line Algorithms 2004 |
english