Archiwum seminariów

Bartosz Wodziński
Optymalizacja Kombinatoryczna
On the unique games conjecture

For many hard problems, instead of solving them directly, we need good approximation algorithms. Apart from good their time complexity and decent approximation factor guarantee, we would like to know whether they achieve the best possible approximation ratio (assuming P ≠ NP) possible. Unfortunately, for many NP-complete problems, there is a huge gap between best-known approximation ratio and the ratio that is proved to be unachievable in polynomial time. For instance, for Vertex Cover problem, we don't know any algorithm having a better ratio than 2, and it has been proved in 2005 that it is impossible to get a better ratio than ~1.36. As an attempt to fill in this gap, in 2002, the so-called Unique Games Conjecture was formulated by Khot. It states that having a (1-𝜀)-satisfiable instance of Unique Label Cover problem, it is NP-hard to find a solution satisfying even epsilon fraction of constraints. Assuming it, we are able to prove many tight inapproximability results, for example, it implies that Goemans-Williamson Algorithm for Max-Cut problem achieves the best possible approximation rate. It also follows that we cannot get any better ratio than 2 in the case of Vertex Cover problem. The Unique Games Conjecture is an unusual open problem since the academic world is about evenly divided on whether it is true or not. During the seminar, I will cover this conjecture in more details giving more examples of its influence and presenting recent progress in order to prove it.

  1. Subhash Khot. On the Unique Games Conjecture (Invited Survey). 2010 IEEE 25th Annual Conference on Computational Complexity, Cambridge, MA, 2010, pp. 99-121.
  2. Bartosz Wodziński. Unique Games Conjecture. slides. 2020.

(the seminar will only be online)

Rafał Byczek
Optymalizacja Kombinatoryczna
Wegner’s conjecture - colouring the square of a planar graph

The square G2 of a graph G is the graph with the same vertex set in which two vertices are joined by an edge if their distance in G is at most two. The chromatic number of the square of a graph G is between D + 1 and D+ 1, where D is the maximum degree of G. Equivalently, the square coloring of a graph is to color the vertices of a graph at distance at most 2 with different colors.

In 1977, Gerd Wegner proved that the square of cubic planar graphs is 8-colorable. He conjectured that his bound can be improved - the chromatic number of G2 is at most 7, if D = 3, at most D + 5, if 4 ≤ D ≤ 7, and [3D / 2] + 1, otherwise. Wegner also gave some examples to illustrate that these upper bounds can be obtained.

C. Thomassen (2006) proved the conjecture is true for planar graphs with D = 3. The conjecture is still open for planar graphs with D ≥ 4. However several upper bounds in terms of maximum degree D have been proved as follows. In 1993, Jonas proved that χ(G2) ≤ 9D-19, for planar graphs with D ≥ 5. Agnarsson and Halldorson showed that for every planar graph G with maximum degree D ≥ 749, χ(G2) ≤ [9D / 5] + 2. Van den Heuvel and McGuinness (2003) showed that χ(G2) ≤ 2D + 25, Bordin (2002) proved that χ(G2) ≤ [9D / 5] + 1, if D ≥ 47, and Molloy and Salavatipour (2005) proved χ(G2) ≤ [5D / 3] + 78, moreover, χ(G2) ≤ [5D / 3] + 25 if D ≥ 241. Moreover, conjecture is confirmed in the case of outerplanar graphs and graphs without K4 minor.

The aim of the seminar will be to present the main facts about Wegner’s conjecture and main techniques and ideas which were used to prove some upper bounds. The presentation will be based on my master thesis.

  1. Rafał Byczek. Wegner’s conjecture Colouring the square of a planar graph. slides. 2020.

(the seminar will only be online)

Szymaon Kapała
Podstawy Informatyki
Searching for shortest and least programs by Cristian Caludea, Sanjay Jain, Wolfgang Merkle and Frank Stephan
The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U(p) =x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f(x) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I_1, I_2, ...of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I_n to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets I_n are not too small.

Poprzednie referaty

Adam Polak
Informatyka Teoretyczna
Monochromatic triangles, intermediate matrix products, and convolutions

The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(nω) time algorithms, for ω<2.373. On the other hand, the (min,+)-product, which is at the heart of APSP, is widely conjectured to require cubic time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems, e.g. the (min,max)-product, the min-witness product, APSP in directed unweighted graphs. The best runtimes for these "intermediate" problems are all O(n(3+ω)/2). A similar phenomenon occurs for convolution problems.

Can one improve upon the running times for these intermediate problems? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way?

We make progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and min-witness product can be reduced to both the (min,max)-product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is equivalent to the famous 3SUM problem. As this variant is in O(n3/2) time and 3SUM is in O(n2) time, our result gives the first fine-grained equivalence between natural problems of different running times.

Joint work with Andrea Lincoln and Virginia Vassilevska Williams.

Piotr Mikołajczyk
Podstawy Informatyki
Satisfiability in Strategy Logic can be Easier than Model Checking by Erman Acar, Massimo Benerecetti and Fabio Mogavero.

In the design of complex systems, model-checking and satisfiability arise as two prominent decision problems. While
model-checking requires the designed system to be provided in advance, satisfiability allows to check if such a system even exists. With very few exceptions, the second problem turns out to be harder than the first one from a complexity-theoretic standpoint. In this paper, we investigate the connection between the two problems for a non-trivial fragment of Strategy Logic (SL, for short). SL extends LTL with first-order quantifications over strategies, thus allowing to explicitly reason about the strategic abilities of agents in a multi-agent system. Satisfiability for the full logic is known to be highly undecidable, while model-checking is non-elementary.

The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important game-theoretic properties of multi-agent systems, such as existence of Nash and immune equilibria, as well as to formalize the rational synthesis problem. We show that satisfiability for such a fragment is PSPACE-COMPLETE, while its model-checking complexity is 2EXPTIME-HARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctive-binding first-order logic, a recently discovered decidable fragment of first-order logic.

Piotr Helm, Krzysztof Zysiak

Optimal Sorting with Persistent Comparison Errors [B. Geissmann et al.]
Rozważamy problem sortowania n elementów w przypadku stałego błędu porównań. W tym problemie, każde porównanie między dwoma elementami może się pomylić ze stałym (małym) prawdopodobieństwem, i porównania nie mogą zostać powtórzone. Perfekcyjne posortowanie w tym modelu jest niemożliwe i celem jest zminimalizowanie dyslokacji każdego z elementów w zwróconym ciągu, czyli odległość od jego poprawnej pozycji. Istniejące ograniczenia dolne dla tego problemu pokazują, że żaden algorytm nie zagwarantuje z wysokim prawdopodobieństwem maksymalnej i sumarycznej dyslokacji lepszej niż Ω(logn) i Ω(n), odpowiednio, bez względu na czas działania.
W tej pracy, prezentujemy pierwszy sortujący algorytm o złożoności O(n log n), który gwarantuje zarówno maksymalna dyslokację O(log n), jak i sumaryczną dyslokację O(n) z wysokim prawdopodobieństwem. To rozstrzyga złożoność czasową tego problemu i pokazuje, że błędy porównań nie zwiększają jego złożoności czasowej: ciąg z najlepszą możliwą dyslokacją może zostać uzyskany w czasie O(n logn), i nawet bez błędów porównań czas Ω(n log n) jest konieczny, by zagwarantować takie ograniczenia dyslokacji.
Aby osiągnąć ten optymalny wynik, rozwiązujemy dwa podproblemy, za pomocą metod, które mogą mieć dalsze, osobne zastosowania. Jednym z nich jest zlokalizowanie pozycji, na którą należy wstawić element do prawie posortowanego ciągu o dyslokacji O(log n)  w taki sposób, aby dyslokacja zwracanego ciągu wciąż była O(logn). Drugi problem - jak równocześnie wstawić m elementów w prawie posortowany ciąg innych m elementów, tak aby zwracany ciąg 2m elementów pozostał prawie posortowany.
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Majority choosability of digraphs

One of the variations of graph coloring is the assignment of colors to vertices such that for each v vertex, at most half of the neighbors v have the same color as v. Such coloring is called the majority coloring of the graph. The goal is to color the graph in the above way with the smallest number of colors. During the presentation various variants of this problem will be discussed, historical results, the latest results, and still intriguing hypotheses. Among other things, the effects of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24 (3), Paper 3.57, 2017.
  6. António Girão, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Šámal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15 – 20, 2019.
Przemysław Rutka (Lublin)
Podstawy Informatyki
Wybrane algorytmiczne zastosowania klasycznych wielomianów ortogonalnych
Klasyczne wielomiany ortogonalne, odpowiadające im klasyczne funkcje wagowe oraz ich własności znajdują wiele zastosowań w takich chociażby obszarach jak tomografia, mechanika kwantowa, kombinatoryka, przetwarzanie obrazów i sygnałów, kompresja danych oraz zwiększanie wydajności algorytmów. W tym ostatnim zakresie cały czas uzyskuje się wiele ciekawych wyników, pozwalających na efektywne numeryczne rozwiązywanie różnych problemów. Można do tych problemów w szczególności zaliczyć barycentryczne interpolacje Fejéra, Hermite'a i Lagrange'a oraz problemy ekstremalne typu Szegő i Markowa-Bernsteina. W pierwszym przypadku, gdy interpolowanych jest n wartości w węzłach, będących zerami klasycznych wielomianów ortogonalnych, możliwa jest poprawa złożoności obliczeniowej algorytmów, obliczających wartości wielomianów interpolacyjnych w oparciu o wzory barycentryczne, z O(n^2) do O(n). Wymagane jest w tym celu zastosowanie odpowiednich jawnych wzorów na wagi barycentryczne lub wzorów wiążących wagi barycentryczne z wagami i węzłami kwadratur Gaussa. Z kolei w drugim przypadku, jak się okazuje powiązanym z pierwszym, daje się sformułować wzory, pozwalające bezpośrednio obliczać na komputerze najlepsze stałe, występujące w nierównościach typu Szegő i Markowa-Bernsteina oraz wartości wielomianów ekstremalnych, dla których te nierówności stają się równościami. Nierówności te związane są z iterowanymi klasycznymi funkcjami wagowymi i można je wykorzystać do szacowania wartości lub norm pochodnych D^{k}p lub różnic progresywnych Δ^{k}p wielomianów p(x), odpowiednio w przypadku ciągłym lub dyskretnym.
     Inne tego typu rezultaty, korzystające z klasycznych wag i/lub klasycznych wielomianów ortogonalnych, można otrzymać także dla problemu typu izoperymetrycznego w klasie płaskich, zamkniętych krzywych wielomianowych, problemu równowagi elektrostatycznej układu ładunków, problemu efektywnej, stabilnej i najbardziej ekonomicznej interpolacji oraz problemu dwustronnych oszacowań aproksymacyjnych a priori typu Chernoffa.
Bartłomiej Bosek
Informatyka Teoretyczna
Algorithms for posets and graphs games – coloring and matching

Graph colorings and online algorithms on graphs constitute the key fragments of the algorithmic graph theory. Specifically, the subject of this study will be a presentation of the results concerning

  • different variants of coloring of graphs and partially ordered sets,
  • online coloring of partially ordered sets,
  • incremental matchings of bipartite graphs.

The first part of the talk will concern different aspects of the coloring problem as well as different evidential techniques. The presented results concern majority choosability of digraphs, harmonious coloring of hypergraphs and semi-uni conjecture of product of two posets. The next part of presentation will concern online chain partitioning of posets. There will be presented a full characterization of the class of posets, for which the number of colors (chains) used by first-fit is a function of width, i.e. best offline solution. This part will also present two different subexponential online algorithm for the online chain partitioning problem. The last part will concern the incremental matching problem in bipartite graphs. There will be presented an incremental algorithm that maintains the maximum size matching in total time equal the running time of one of the fastest offline maximum matching algorithm that was given by Hopcroft and Karp. Moreover, I will show an analysis of the shortest augmenting path algorithm.

This is joint work with Marcin Anholcer, Jarosław Grytczuk, Sebastian Czerwiński, Paweł Rzążewski, Stefan Felsner, Kolja Knauer, Grzegorz Matecki, Tomasz Krawczyk, H. A. Kierstead, Matthew Smith, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz.

Michał Wrona
Informatyka Teoretyczna
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by first-order expansions of countably infinite homogeneous graphs, that are, the structures first-order-definable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H.

Our main result is that structures under consideration have relational width exactly (2,L) where L is the maximal size of a forbidden subgraph in S, but not smaller than 3. It implies, in particular, that the CSP parametrized by such structures may be solved in time O(nm) where n is the number of variables and m is the maximum of L and the arities of relations in the signature, while strict width l ensures time O(nl+1). Furthermore, since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures, in which case, if finite, relational width is always at most (2,3). 

Finally, we show that certain maximally tractable constraint languages with a first-order definition in a countably infinite homogeneous graph whose CSPs are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, providing an alternative algorithm for already studied problems.

Rafał Byczek, Bruno Pitrus

Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów.

Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2-δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym.

W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)).

Bartłomiej Bosek
Optymalizacja Kombinatoryczna
A new variant of the game of cops and robber

We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,...,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,2,...,dk) whose components di=dG(u,vi), i=1,2,...,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localise him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously. The aim of the talk is to present results concerning 2-trees, outerplanar graphs and planar graphs. This is a joint work with Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, and Małgorzata Śleszyńska-Nowak.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Centroidal localization game. arXiv, pages 1-15, 2017.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Localization game on geometric and planar graphs. arXiv, pages 1-15, 2017.

Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Local Dimension is Unbounded for Planar Posets

In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter.

Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017.

Bruno Pitrus
Podstawy Informatyki
Linear lambda terms as invariants of rooted trivalent maps by Noam Zeilberger

The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.



Dawid Pyczek i Jakub Rówiński
Podstawy Informatyki
Asymptotic Density and the Theory of Computability by CARL JOCKUSCH AND PAUL SCHUPP
The purpose of this paper is to survey recent work on how classical asymptotic density interacts with the theory of computability. We have tried to make the survey accessible to those who are not specialists in computability theory and we mainly state results without proof, but we include a few
easy proofs to illustrate the flavor of the subject. In complexity theory, classes such as P and NP are defined by using worst-case measures. That is, a problem belongs to the class if there is an algorithm solving it which has a suitable bound on its running time over all instances of the problem. Similarly, in computability theory, a problem is classified as computable if there is a single algorithm which solves all instances of the given problem. There is now a general awareness that worst-case measures may not give a good picture of a particular algorithm or problem since hard instances may be very sparse. The paradigm case is Dantzig’s Simplex Algorithm for linear programming problems. This algorithm runs many hundreds of times every day for scheduling and transportation problems, almost always very quickly. There are clever examples of Klee and Minty showing that there exist instances for which the Simplex Algorithm must take exponential time, but such examples are not encountered in practice. Observations of this type led to the development of average-case complexity by Gurevich and by Levin independently. There are different approaches to the average-case complexity, but they all involve computing the expected value of the running time of an algorithm with respect to some measure on the set of inputs. Thus the problem must be decidable and one still needs to know the worst-case complexity. Another example of hard instances being sparse is the behavior of algorithms for decision problems in group theory used in computer algebra packages. There is often some kind of an easy “fast check” algorithm which quickly produces a solution for “most” inputs of the problem. This is true even if the worst-case complexity of the particular problem is very high or the problem is even unsolvable. Thus many group-theoretic decision problems have a very large set of inputs where the (usually negative) answer can be obtained easily and quickly.
Tomasz Krawczyk
Informatyka Teoretyczna
Representation and coloring of partially ordered sets under conditions of incomplete information

The purpose of my talk is to discuss several problems related to coloring and construction of appropriate representation for partially ordered sets (also posets) and graph classes derived from posets. In these problems, we will assume the following two scenarios:

in the first scenario, an algorithm receives a poset element one after another. For each new element added, the algorithm takes an irrevocable decision (assigns a color or extends a current representation) just after this element is presented (algorithms that work under such conditions are called on-line).

in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs.

In the context of on-line algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of on-line coloring of incomparability graphs, and embedding posets into d-dimentional space Rd.

In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs.

We focus our attention on:

  • function graphs that are intersection graphs of continuous functions [0,1] R,

  • permutation graphs that are intersection graphs of linear functions [0,1] R,

  • trapezoid graphs that are intersection graphs of trapezoids spanned between two fixed parallel lines containing the bases of these trapezoids.

Marcin Pilipczuk
University of Warsaw
Informatyka Teoretyczna
Subexponential Parameterized Algorithms for Planar Graphs, Apex-Minor-Free Graphs and Graphs of Polynomial Growth via Low Treewidth Pattern Covering

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

1) A induces a subgraph of G of treewidth O(√k log k), and

2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log2k)nO(1))−1, where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log2k)nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Michał Pilipczuk, and Saket Saurabh: and

Yauheni Ananchuk
Podstawy Informatyki
Binary Constraint Problems have traditionally been considered as Network Satisfaction Problems over some relation algebra. A constraint network is satisfable if its nodes can be mapped into some representation of the relation algebra in such a way that the constraints are preserved. A qualitative representation is like an ordinary representation, but instead of requiring (a ; b) = a j b , as we do for ordinary representations, we only require that. A constraint network is qualitatively satisfable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfable then it is clearly qualitatively satisfable, but the converse can fail.
However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfable if and only if it is qualitatively satisfable. Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over non-associative algebras. We prove that computationally, qualitative representations have many advantages over
ordinary representations: whereas many finite relation algebras have only infnite representations, every finite qualitatively representable algebra has a finite qualitative representation; the representability problem for (the atom structures of) finite non-associative algebras is NP-complete; the network satisfaction problem over a finite qualitatively representable algebra is always ; the validity of equations over qualitative representations is co-NP-complete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebra
Piotr Danilewski
Informatyka Teoretyczna
Functional Code Building

A typical language translator uses a parser to convert an input string into some internal representation, usually in a form of an AST. The AST is then analyzed and transformed in passes. In the final pass, the AST is converted into the output, be it a machine code or source code of another language.
However, if we try to combine different languages, e.g. for a purpose of a multi-domain project, we may have a problem: each language uses different kinds of AST nodes, has different assumptions on the AST structure and features different pass algorithms. Settling for the common ground by limiting the node types, assumptions, and algorithms limits how the languages may reason about their code. Any high-level information is lost in such representation and high-level transformations cannot be defined.
Working on the common AST is similar to unstructured programming: AST acts as a global machine state. Any change to the state, e.g. introduced by a new language, may inadvertely affect the behavior of the existing languages. In regular programming we have moved away from unstructured programming towards higher abstraction levels, e.g. through functional programming. If it can be done to regular programming, can it be done to AST and code builders as well?
Our solution treats AST nodes not as objects of a fixed type. Instead, it is a function with its body describing entirely the behavior of such node. Even the connection between the nodes is represented internally by the function, in a form of continuations. 
The passes over the AST are replaced by a single invocation of these functions. The node functions may contain code for multiple stages of code analysis. In order to reduce the run time these additional stages are scheduled through dynamic staging.
This gives the power of abstraction to code building. Even nodes come from different languages may interact, as long as they understand the passed arguments.
This major change on how a code is represented requires changes in how we think about common basic operations during language interpretation:
- how do we link two nodes/functions together?
- how do we create control flow structures?
- how do we perform name lookups, even across different languages?
- how do we optimize the code so that the AST layer dissapears when generating code?
- what language-specific optimizations can be performed and how do we specify them?
We will address these questions in the upcoming talk.

Tomasz Kisielewski
Podstawy Informatyki
Programy które są w stanie przeprowadzać rozumowania o swoich własnościach
Proving properties of programs within their language

Przedstawię wstępną wersję swojego programu badawczego, mającego
na celu umożliwienie dowodzenia własności programów w języku, w
którym są napisane. Zacznę od motywacji, opierającej się o pewne
rozwiązanie zmodyfikowanego dylematu więźnia, w której graczami
są programy mające dostęp do kodu źródłowego drugiego gracza.
Następnie przybliżę obecny stan automatycznego dowodzenia faktów
o programach, ze szczególnym uwzględnieniem silnie typowanych
języków funkcyjnych. Na koniec przedstawię dalekosiężne cele i
największe trudności, których należy się spodziewać przy
implementacji efektywnych funkcji dowodzących fakty o programach.


I will present an initial version of my research program, whose

main goal is to enable proving properties about programs within
the language they are written in. My motivation is based on a
specific solution to the open-source prisoner's dilemma, where
the players are programs with access to the other player's source
code. After explaining the motivation I will shortly present the
current state of automatic proving of programs' properties, with
emphasis on strongly typed functional languages. Finally, I will
introduce my long term goals and the main challenges one should
expect to face when implementing an effective function for
proving facts about programs.

Kamil Pietruszka
Podstawy Informatyki
Regular Combinators for String Transformations by Rajeev Alur Adam Freilich Mukund Raghothaman

We focus on (partial) functions that map input strings to a monoid such as the set of integers with addition and the set of output strings with concatenation. The notion of regularity for such functions has been defined using two-way finite-state transducers, (one-way) cost register automata, and MSO-definable graph transformations. In this paper, we give an algebraic and machine-independent characterization of this class analogous to the definition of regular languages by regular expressions. When the monoid is commutative, we prove that every regular function can be constructed from constant functions using the combinators of choice, split sum, and iterated sum, that are analogs of union, concatenation, and Kleene *, respectively, but enforce unique (or unambiguous) parsing. Our main result is for the general case of non-commutative monoids, which is of particular interest for capturing regular string-to-string transformations for document processing. We prove that the following additional combinators suffice for constructing all regular functions:

(1) the left-additive versions of split sum and iterated sum, which allow transformations such as string reversal;

(2) sum of functions, which allows transformations such as copying of strings; and

(3) function composition, or alternatively, a new concept of chained sum, which allows output values from adjacent blocks to mix.

Michał Zieliński
Podstawy Informatyki
Beta Reduction is Invariant, Indeed by Beniamino Accattoli and Ugo Dal Lago

Slot and van Emde Boas weak invariance thesis states that reasonable machines can simulate each other within a polynomially overhead in time.Is lambda  calculus a reasonable machine? Is there a way to measure the computational complexity of a lambda term? This paper presents the first complete positive answer to this longstanding problem. Moreover, our answer is completely machineindependent and based over a standard notion in the theory of lambda calculus: the length of a leftmost-outermost derivation to normal form is an invariant cost model. Such a theorem cannot be proved by directly relating lambda calculus with Turing machines or random access machines, because of the size explosion problem: there are terms that in a linear number of steps produce an exponentially long output. The first step towards the solution is to shift to a notion of evaluation for which the length and the size of the output are linearly related. This is done by adopting the linear substitution calculus (LSC), a calculus of explicit substitutions modelled after linear logic proof nets and admitting a decomposition of leftmostoutermost
derivations with the desired property. Thus, the LSC is invariant with respect to, say, random access machines. The second step is to show that LSC is invariant with respect to the lambda calculus. The size explosion problem seems to imply that this is not possible:having the same notions of normal form, evaluation in the LSC is exponentially longer than in the lambda calculus. We solve such an impasse by introducing a new form of shared normal form and shared reduction, deemed useful. Useful evaluation avoids those steps that only unshare the output without contributing to bata redexes, i.e. the steps that cause the blow-up in size. The main technical contribution of the paper is indeed the definition of useful reductions and the thorough analysis of their properties.

Piotr Bejda
Optymalizacja Kombinatoryczna
Perfect matchings in O(n log n) time in regular bipartite graphs

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bi-partite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m*sqrt(n)). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved first to O'(min(m, n^2.5/d)) and then to O'(min(m,n^2/d)). It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, an d is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for any deterministic algorithm. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log2 n) time, with O(m) pre-processing time; this gives a simple O(m + mn log2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix.

A. Goel and M. Kapralov and S. Khanna, Perfect matchings in O n log n time in regular bipartite graphs

Ariel Gabizon
Technion, Israel
Informatyka Teoretyczna
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

A probabilistically checkable proof (PCP) enables, e.g., checking the satisfiability of a 3-SAT formula ɸ, while only examining a constant number of locations in the proof. A long line of research led to the construction of PCPs with length that is quasi-linear in n := |ɸ|.

In a zero knowledge PCP with knowledge bound K, reading any K symbols of the proof reveals no additional information besides the validity of the statement; e.g., no information is revealed about the assignment satisfying ɸ. Kilian, Petrank, and Tardos gave a transformation from any PCP into a ZK-PCP with knowledge bound K, for any desired K. A drawback of their transformation is that it requires multiplying the proof length by a factor of (at least) K^6.

In this work, we show how to construct PCPs that are zero knowledge for knowledge bound K and of length quasilinear in K and n, provided that the prover is forced to write the proof in two rounds. In this model, which we call duplex PCP (DPCP), the verifier gets an oracle string from the prover, then replies with some randomness, and then gets another oracle string from the prover, and it can make up to K queries to both oracles.

Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but rely on algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure (which many constructions have, including [BFLS91,ALMSS98,BS08]) we can add the zero knowledge property at virtually no cost while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.

Joint work with Eli Ben-Sasson, Alessandro Chiesa and Madars Virza
Paweł Zegartowski
Informatyka Teoretyczna
Cache-Oblivious Hashing
The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t_q=1+1/2^Ω(b) disk accesses for any load factor α bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases.

We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t_q=1+Θ(α/b) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547558, 2011) achieves t_q=1+1/2^Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Note that the two conditions hold on a real machine, although they are not stated in the cacheoblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t_q=1+O(α/b), which is exactly what linear probing achieves.  

Rasmus Pagh, ZheweiWei, Ke Yi, Qin Zhang, Cache-Oblivious Hashing, Algorithmica (2014) 69:864-883
Maciej Bendkowski
Informatyka Teoretyczna
Contention Resolution under Selfishness
In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is the study of distributed transmission and retransmission protocols designed to maximize notions of utility such as channel utilization in the face of blocking communications.

An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA'07, pp.179188, SIAM, Philadelphia 2007) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs.

In this paper we treat the case of non-zero transmission cost c.We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected cost Θ(n+c·log n) and is in o(1)-equilibrium, where n is the number of users.  

George Christodoulou, Katrina Ligett, Evangelia Pyrga, Contention Resolution under Selfishness, Algorithmica (2014) 70:675693
Piotr Danilewski Universität des Saarlandes
Informatyka Teoretyczna
AnyDSL - a host for any language
In a multi-domain project, there is no single programming language that can be used to program everything. Instead, a combination of general-purpose and domain-specific languages (DSLs) are used. Unfortunately, many domains lack a good, representative DSL, due to domain diversity and difficulty of creating a new compiler. Moreover, the communication across the languages is limited, often requiring the data to be serialized, and reducing the quality of optimization and compile-time verification.

In our talk we present our approach to solve these problems, by introducing a new metamorphic language - AnyDSL. The parsing and execution of AnyDSL can be interleaved and the latter can influence the former - e.g. by introducing a new grammar with which parsing should resume. Regardless of the language the source is written in, all code is translated into a low-level, functional representation in continuous passing style (AIR). AIR serves as a "meeting point", permitting inter-DSL communication. AIR can be interpreted or compiled to LLVM bytecode and then to machine code.

New grammars are defined also within AnyDSL. Unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies. With it the overhead of having multiple layers of languages can be resolved early. It also allows the DSL designer to specify domain specific optimizations. After all those transformations, AIR can be compiled to machine code that is efficient, with performance comparable to programs written in general-purpose languages.

In our talk we present a new metamorphic language - AnyDSL. AnyDSL permits the native parser to be exchanged with a custom DSL. Regardless of the DSL however, all code is translated into a low-level, functional representation in continuous passing style (AIR).

New grammars are defined also within AnyDSL, but unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies to resolve overheads and define domain specific optimizations. AIR can be compiled to machine code, and produced programs have performance comparable to those produced by general-purpose languages.  

Andrzej Dorobisz
Informatyka Teoretyczna
Scheduling parallel jobs to minimize the makespan
We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen.

List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.  

Johannes Berit, Scheduling parallel jobs to minimize the makespan, J of Schedulling, 9(2006), 433–452
Maciej Gazda Eindhoven University of Technology
Podstawy Informatyki
Zielonka's Recursive Algorithm for Parity Games
Parity games are infinite duration, two player games played on a finite directed graph. Vertices of the graph are labelled with natural numbers (called priorities) and the winning condition is determined by the parity of the most significant (typically maximal) priority encountered inifnitely often. The games are memoryless determined, moreover, the problem of finding the winning partition of a given game belongs to both NP and coNP complexity classes. On the other hand, no polynomial algorithm solving parity games has been found (the best one due to Jurdziński, Paterson and Zwick has subexponential running time with sqrt(n) in the exponent). In my talk, I will give a brief introduction to this intriguing computational problem, and then focus on one of the earliest and simplest solving algorithms, namely Zielonka's recursive algorithm. Even though its worst-case running time is not particularly impressive as compared to more sophisticated solvers, the experimental study of Friedmann and Lange has shown that in practice it works very well. In order to understand why it is the case, in our recent work with Tim Willemse we have analysed the performance of two variants of the algorithm (standard and optimised) on certain subclasses of parity games (dull, weak, and solitaire). Moreover, we have provided a tighter lower bound on its worst-case running time.  
Bartłomiej Ryniec
Informatyka Teoretyczna
Preprocess, Set, Query!
Thorup and Zwick (J.ACM 52(1):1–24, 2005 and STOC'01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k ≥ 1 it is possible to preprocess the graph in O˜(m n^{1/k}) time and generate a compact data structure of size O(k n^{1+1/k}). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k−1 in O(k) time. For k=2 this gives an oracle of O(n^{1.5}) size that produces in constant time estimated distances with stretch 3.
Recently, Patrascu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n^{5/3}) size that produces in constant time estimated distances with stretch 2.
In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs.We present a data structure that produces estimated distances with 1+ε stretch. The size of the data structure is O(n m^{1−ε'}) and the query time is O˜(m^{1−ε'}). Using it for sparse unweighted graphs we can get a data structure of size O(n^{1.87}) that can supply in O(n^{0.87}) time estimated distances with multiplicative stretch 1.75.  
Ely Porat, Liam Roditty, Preprocess, Set, Query! Algorithmica (2013) 67:516–528
Igor Adamski
Informatyka Teoretyczna
Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2^w nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(|P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log|T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the LZ78 encoding of a given string of length n over an alphabet of size σ in sublinear (o(n)) time and sublinear (o(n log σ) bits) working space for small alphabets
(σ = 2^{o(log n \cdot \frac{log log log n}{(log log n)^2})).
Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size.  
Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung, Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, Algorithmica DOI 10.1007/s00453-013-9836-6
W. Hugh WoodinUC Berkeley
Informatyka Teoretyczna
The Continuum Hypothesis and the search for Mathematical Infinitynew place and date: Oct 14, 2013, 16:00,Polska Akademia Umiejętności, Kraków, Sławkowska 17
By middle of the 20th century the problem of the Continuum Hypothesis was widely regarded as one of the prominent problems in all of Mathematics. Remarkably, this question cannot be solved on the basis of the basic principles (these are the ZFC axioms) on which the entire subject is based. This discovery of Cohen, 50 years ago this summer, is arguably one of the major discoveries in the history of modern Mathematics.

But does this mean that the question of the Continuum Hypothesis has no answer? Any "solution" must involve the adoption of new principles but which principles should one adopt? Alternatively, perhaps the correct assessment of Cohen's discovery is that the entire enterprise of the mathematical study of Infinity is ultimately doomed because the entire subject is simply a human fiction without any true foundation. In this case, any "solution" to the Continuum Hypothesis is just an arbitrary (human) choice.

Over the last few years a scenario has emerged by which with the addition of a single new principle not only can the problem of the Continuum Hypothesis be resolved, but so can all of the other problems  which Cohen's method has been used to show are also unsolvable (and there have been many such problems).  Moreover the extension of the basic (ZFC) principles by this new principle would be seen as an absolutely compelling option based on the fundamental intuitions on which the entire mathematical conception of Infinity is founded.

However, this scenario critically depends upon the outcome of a single conjecture. If this conjecture is false then the entire approach, which is the culmination of nearly 50 years of research, fails or at the very least  has to be significantly revised.

Thus the mathematical study of Infinity has arguably reached a tipping point. But which way will it tip?  

Sebastian Syta
Informatyka Teoretyczna
A Sublinear Time Algorithm for PageRank Computations
In a network, identifying all vertices whose PageRank is more than a given threshold value $\Delta$ is a basic problem that has arisen in Web and social network analyses. In this paper, we develop a nearly optimal, sublinear time, randomized algorithm for a close variant of this problem. When given a directed network \graph, a threshold value $\Delta$, and a positive constant $c>3$, with probability $1-o(1)$, our algorithm will return a subset $S\subseteq V$ with the property that $S$ contains all vertices of PageRank at least $\Delta$ and no vertex with PageRank less than $\Delta/c$. The running time of our algorithm is always $\tilde{O}(\frac{n}{\Delta})$. In addition, our algorithm can be efficiently implemented in various network access models including the Jump and Crawl query model recently studied by \cite{brautbar_kearns10}, making it suitable for dealing with large social and information networks. As part of our analysis, we show that any algorithm for solving this problem must have expected time complexity of ${\Omega}(\frac{n}{\Delta})$. Thus, our algorithm is optimal up to logarithmic factors. Our algorithm (for identifying vertices with significant PageRank) applies a multi-scale sampling scheme that uses a fast personalized PageRank estimator as its main subroutine. For that, we develop a new local randomized algorithm for approximating personalized PageRank which is more robust than the earlier ones developed by Jeh and Widom \cite{JehW03} and by Andersen, Chung, and Lang \cite{AndersenCL06}.  
Christian Borgs, Michael Brautbar, Jennifer Chayes1, and Shang-Hua Teng, A Sublinear Time Algorithm for PageRank Computations,
Tomasz Kołodziejski
Informatyka Teoretyczna
8/5 Approximation for TSP Paths
We prove the approximation ratio 8/5 for the metric s-t-Path-TSP problem, and more generally for shortest connected T-joins. The algorithm that achieves this ratio is the simple ``Best of Many'' version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides s-t-tour out of those constructed from a family Fscr_{>0} of trees having a convex combination dominated by an optimal solution x^* of the fractional relaxation. They give the approximation guarantee sqrt{5}+1/2 for such an s-t--tour, which is the first improvement after the 5/3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13/8-approximation of shortest connected T-joins, for |T|≥4.

The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing x^*/2 in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in Fscr_{>0} into an s-t--path (or more generally, into a T-join) and its complement, which induces a decomposition of x^*. This decomposition can be refined and then efficiently used to complete x^*/2 without using linear programming or particular properties of T, but by adding to each cut deficient for x^*/2 an individually tailored explicitly given vector, inherent in the problem.

A simple example shows that the Best of Many Christofides algorithm may not find a shorter s-t--tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.  

András Sebö, Eight-Fifth Approximation for TSP Paths, Integer Programming and Combinatorial Optimization, LNCS7801, 2013, pp 362-374