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
  • Feb. 17, 2011, 12:15 p.m.
    dr hab Jerzy Tyszkiewicz (Uniwersytet Warszawski)
    Almost) the Sam
    In the talk I will describe a mild syntactic restriction concerning spreadsheets (created in e.g. MS Excel or OpenOffice), which turns them into a computing device almost equivalent to Parallel Random Access Machines. Under this …
  • Jan. 20, 2011, 12:15 p.m.
    Jarosław Grytczuk (Uniwersytet Jagielloński)
    Nonrepetitive coloring games
    Nonrepetitive coloring games can be played on various combinatorial structures (graphs, words, etc.). Basic idea goes back to Thue, who proved in 1906 that the ntegers can be 3-colored so that any two adjacent segments …
  • Jan. 13, 2011, 12:15 p.m.
    - (Uniwersytet Warszawski)
    Seminarium odwołane
  • Dec. 16, 2010, 12:15 p.m.
    Krzysztof Onak (CMU)
    Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
    We present a near-linear time algorithm for approximating the edit distance between two strings to within a significantly better factor than previously known. This result emerges in our investigation of edit distance from a new …
  • Dec. 9, 2010, 12:15 p.m.
    Łukasz Kowalik (Uniwersytet Warszawski)
    Cykl Hamiltona w grafach nieskierowanych szybciej niz 2^n.
    Problemy cyklu Hamiltona i TSP to jedne z najintensywniej badanych problemow optymalizacyjnych. W latach 60-tych Held i Karp podali prosty algorytm oparty na programowaniu dynamicznym, wymagajacy czasu O*(2^n) i pamieci O(2^n). Powstalo naturalne pytanie, czy …
  • Dec. 2, 2010, 12:15 p.m.
    Maxime Crochemore (King's College London)
    Reactive Automata
  • Nov. 25, 2010, 12:15 p.m.
    Bartlomiej Bosek i Tomasz Krawczyk (Uniwersytet Jagielloński)
    The sub-exponential upper bound for the on-line chain partitioning problem
    One of the important models for scheduling is based on partially ordered sets. In this model the points represent the incoming tasks and the order reflects cause-effect relation between tasks. The algorithmic problem which arises …
  • Nov. 4, 2010, 12:15 p.m.
    Marcin Pilipczuk (Uniwersytet Warszawski)
    Unique Games Conjecture i trudność aproksymacji
     Począwszy od sławnego twierdzenia PCP, do dnia dzisiejszego znamy bardzo dużo wyników dowodzących trudność aproksymacji różnych problemów. O ile dowodzenie braku istnienia PTASa jest zazwyczaj mniej lub bardziej skomplikowaną redukcją kombinatoryczną, o tyle otrzymani ścisłych …
  • Oct. 21, 2010, 12:15 p.m.
    Jakub Łącki (Uniwersytet Warszawski)
    Dynamiczne algorytmy dla silnie spójnych składowych i domknięcia przechodniego
    Zaprezentuję strukturę danych, która utrzymuje strukturę silnie spójnych składowych grafu skierowanego i obsługuje operacje usunięć krawędzi. Przy jej użyciu pokażę algorytm utrzymywania domknięcia przechodniego podczas usuwania krawędzi z grafu. Działa on deterministycznie i jest równie …
  • Oct. 14, 2010, 12:15 p.m.
    Jakub Pawlewicz (Uniwersytet Warszawski)
    Zliczanie liczb bezkwadratowych
    Liczba bezkwadratowa, to taka, która nie ma dzielników kwadratowych Liczenie liczby liczb bezkwadratowych nie większych od n dotychczas potrafiliśmy robić w czasie O(n^1/2). Przedstawię algorytm działający w czasie O(n^2/5) w pamięci O(n^1/5), który dodatkowo dobrze …
  • Oct. 7, 2010, 12:15 p.m.
    Jaroslaw Byrka (Uniwersytet Wrocławski)
    An Improved LP-based Approximation for Steiner Tree
    The Steiner tree problem is: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was …
  • Oct. 9, 2008, 12:15 p.m.
    Piotr Sankowski (Uniwersytet Warszawski)
    Lokalne koalicje w grach na sieciach
    Jakosc equilibrium Nasha w grach na sieciach zostala juz dobrze zrozumiana i seminarium zaczne od wprowadzenia problmu i przypomnienia najwazniejszych wynikow. Natomiast glownym tematem saminarium bedzie cena anarchii w grzach na sieci z kosztem Shaplya, …
  • Nov. 29, 2007, 12:15 p.m.
    David Peleg (Weizmann Institute)
    On time-efficient broadcast in wireless networks
    As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step …
  • Oct. 4, 2007, 4:15 p.m.
    Madhu Sudan (Massachusetts Institute of Technology)
    Sub-linear time algebraic algorithms
    A modern thrust in computing is to design algorithms that take vast amounts of data and try to estimate properties of the data in a "quick and dirty" way. Sub-linear time algorithms is the area …
  • March 8, 2007, 12:15 p.m.
    Uri Zwick (Tel Aviv University)
    prowadzi: Uri Zwick
    How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This …

Careers

Website

© 2024 University of Warsaw. All rights reserved.