You are not logged in | Log in
Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw
Return to the list of seminars

Seminar Algorithms

Research seminar (Fridays, at 14.15 in room 5060)

For schedule or link to online meetings, see https://semalgo.wordpress.com/

If you want to get notifications, sign up to the mailing list algorytmy@mimuw.edu.pl 

Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf

Google calendar: https://calendar.google.com/calendar/embed?src=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw

YouTube cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp

 

 

Organizers

Information

Fridays, 2:15 p.m. , room: 5060

Home page

https://semalgo.wordpress.com/

List of talks
  • Oct. 27, 2011, 12:15 p.m.
    Wojciech Tyczyński (Uniwersytet Warszawski)
    Wykorzystanie teorii automatów do przetwarzania dokumentów XML
    Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. …
  • Oct. 20, 2011, 12:15 p.m.
    Attila Bernáth (Uniwersytet Warszawski)
    Degree-bounded spanning trees and matroids
    Consider the problem of finding a minimum cost spanning tree in a graph with the additional requirement that the degree of each node in the tree should not exceed an upper bound given in advance. …
  • June 2, 2011, 12:15 p.m.
    Saket Saurabh ( Institute of Mathematical Sciences, Chennai, India)
    Chromatic Coding
    Alon, Yuster and Zwick developed the method of color-coding to give a 2^O(k)n^O(t) time algorithm for subgraph isomorphism problem when the subgraph we are looking for has treewidth t and size k. We develop a …
  • May 12, 2011, 12:15 p.m.
    Jakub Łącki (Uniwersytet Warszawski)
    n log log n) Tim
    We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by …
  • May 5, 2011, 12:15 p.m.
    Piotr Sankowski (Uniwersytet Warszawski)
    Dynamiczne algorytmy tekstowe
    Tematem tego seminarium będzie technika stworzona przez K. Mehlhorn, R. Sundar i C. Uhrigw pracy "Maintaining dynamic sequences under equality tests in polylogarithmic time", która umożliwia dynamiczne utrzymywanie informacji o sekwencjach i pozwala na wykonywanie …
  • April 21, 2011, 12:15 p.m.
    Marek Cygan (Uniwersytet Warszawski)
    Cut&count technique for connectivity problems parameterized by treewidth
    The notion of treewidth, introduced in 1984 by Robertson and Seymour, has in many cases proved to be a good measure of the intrinsic difficulty of various NP-hard problems on graphs, and a useful tool …
  • April 14, 2011, 12:15 p.m.
    Artur Czumaj (University of Warwick)
    Almost Tight Bounds for Reordering Buffer Management
    In this talk we will study the nowadays classical online problem of buffer reordering. In the reordering buffer management problem a stream of colored items arrives at a service station and has to be processed. …
  • April 7, 2011, 12:15 p.m.
    - (Uniwersytet Warszawski)
    Brak seminarium z powodu FIT, OI
  • March 31, 2011, 12:15 p.m.
    Dominik Scheder (ETH Zurich)
    A Full Derandomization of Schoening's k-SAT Algorithm
    Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))). Joint work with …
  • March 31, 2011, 12:15 p.m.
    Dominik Scheder (ETH Zurich)
    A Full Derandomization of Schoenings k-SAT Algorithm
    Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))). Joint work with …
  • March 31, 2011, 12:15 p.m.
    Dominik Scheder (ETH Zurich)
    A Full Derandomization of Schoening's k-SAT Algorithm
    Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time O(a^n * poly(n)) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time O(a^(n+o(n))). Joint work with …
  • March 17, 2011, 12:15 p.m.
    Dariusz Leniowski (Uniwersytet Warszawski)
    Prawdomownosc a budzet w aukcjach -- wynik negatywny i pozytywny.
    Na seminarium zostanie przedstawiony wynik Christiana Borgsa i innych dotyczacy wieloprzedmiotowych aukcji z budzetami. Dla systemow prawdomownych kluczowy okaze sie warunek sprzedzy wszystkich przedmiotow, a jego opuszczenie pozwoli na opracowanie aukcji (asymptotycznie) maksymalizujacej zysk.
  • March 10, 2011, 12:15 p.m.
    Paweł Brach (Uniwersytet Warszawski)
    Rozpowszechnianie plotki w sieciach społecznościowych
    Na seminarium zostanie omówiona grupa algorytmów rozpowszechniania plotki w sieciach społecznościowych. Takie algorytmy używają losowej komunikacji podczas której dochodzi do wymiany informacji pomiędzy węzłami. W omawianym modelu będziemy myśleli o n graczach, którzy w każdej …
  • March 3, 2011, 12:15 p.m.
    Piotr Sankowski (Uniwersytet Warszawski)
    Combinatorial Auctions with Budgets
    We consider budget constrained combinatorial auctions where bidder i has a private value v_i, a budget b_i, and is interested in all the items in S_i. The value to agent i of a set of …
  • Feb. 24, 2011, 12:15 p.m.
    Konstanty Junosza-Szaniawski (Politechnika Warszawska)
    2,1)-labeling of graph
    $L(2,1)$-labeling is a graph coloring model inspired by a channel assignment problem in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least …

Careers

Website

© 2024 University of Warsaw. All rights reserved.