FIT 2017 starts in

  • 00

    days

  • 00

    hours

  • 00

    minutes

  • 00

    seconds

Turing Machine

About FIT 2017

FIT (Forum Informatyki Teoretycznej) is a Polish theoretical computer science meeting organized on yearly basis since 1991. This year the meeting is organized by the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw along with the Warsaw Center of Mathematics and Computer Science on July 7-8, 2017 (Friday-Saturday) in Warsaw. FIT 2017 precedes ICALP 2017 (July 10-14) and follows CPM 2017 (July 4-6).

  • Registration deadline: June 18, 2017 June 28, 2017
  • Conference dates: July 7-8, 2017
Conference Venue

Invited Speakers

event-image

Piotr Indyk

Massachusetts Institute of Technology

Professor in the Theory of Computation Group, MIT Computer Science and Artificial Intelligence Lab. Winner of the Best Student Paper Award at FOCS (2000), Sloan Fellowship, Packard Fellowship, ACM Paris Kanellakis Award and Simons Investigator Award. ACM Fellow. His interests focus on high-dimensional computational geometry, data stream algorithms, sparse recovery, compressive sensing, and sub-linear algorithms.

event-image

Moshe Vardi

Rice University

Karen Ostrum George Distinguished Service Professor in Computational Engineering and Director of the Ken Kennedy Institute for Information Technology. The winner of Godel Prize (2000), a recipient of three IBM Outstanding Innovation Awards and 2008 ACM Presidential Award, among others. His interests focus on automated reasoning, a branch of Artificial Intelligence with broad applications to computer science.

event-image

Tomasz Gogacz

University of Warsaw

Assistant Professor at the University of Warsaw, but his alma mater is University of Wroclaw. The co-winner of 2016 Lipski Prize. His interests focus on use of logic in computer science with particular emphasis on modeling knowledge representation in databases.

event-image

Michał Skrzypczak

University of Warsaw

Assistant Professor at the University of Warsaw. The co-winner of 2016 Lipski Prize. For his doctoral dissertation he received E.W. Beth Dissertation Prize and EATCS Distinguished Dissertation Award. His interests focus on logic and automata theory, especially infinite structures and monadic second-order logic.

Program


9:50
Opening
10:00
Invited talk: Moshe Vardi
The Automated-Reasoning Revolution: From Theory to Practice and Back
For the past 40 years computer scientists generally believed that NP-complete problems are intractable. In particular, Boolean satisfiability (SAT), as a paradigmatic automated-reasoning problem, has been considered to be intractable. Over the past 20 years, however, there has been a quiet, but dramatic, revolution, and very large SAT instances are now being solved routinely as part of software and hardware design. In this talk I will review this amazing development and show how automated reasoning is now an industrial reality.
I will then describe how we can leverage SAT solving to accomplish other automated-reasoning tasks. Counting the the number of satisfying truth assignments of a given Boolean formula or sampling such assignments uniformly at random are fundamental computational problems in computer science with applications in software testing, software synthesis, machine learning, personalized learning, and more. While the theory of these problems has been thoroughly investigated since the 1980s, approximation algorithms developed by theoreticians do not scale up to industrial-sized instances. Algorithms used by the industry offer better scalability, but give up certain correctness guarantees to achieve scalability. We describe a novel approach, based on universal hashing and Satisfiability Modulo Theory, that scales to formulas with hundreds of thousands of variables without giving up correctness guarantees.
The talk is accesible to a general CS audience.

11:00
Coffee break
11:30
Contributed talks - session #1
Marcin Pilipczuk The square root phenomenon, subexponential algorithms, and low treewidth pattern covering in planar graphs
Jan Marcinkowski Approximating MAX-TSP with crayons and kites
Arkadiusz Socała On the fine-grained complexity of rainbow coloring
Konstanty Junosza-Szaniawski Perfect landmark sets in the ALT route planing algorithm
Jarosław Paszek Efficient algorithms for inferring genomic duplication events
Agnieszka Mykowiecka Algorithm for gene-species assignment inference in the presence of horizontal gene transfer
13:00
Lunch
14:00
Invited talk: Tomasz Gogacz
The Chase Termination - decidable and undecidable cases
The Chase procedure is considered as one of the mostimportant tools in database theory. t has been successfully applied to different database problems such as query answering and data exchange. One of the impoortant problems regarding the chase procedure is all-instance termination, that is, given a set of tuple-generating dependencies decide whether the chase terminates for those rules, for every input databa.

15:00
Coffee break
15:30
Contributed talks - session #2
Krzysztof Rządca Optimizing egalitarian performance in the side-effects model of colocation for data center resource management
Anna Gogolińska GPU computations and memory access model based on Petri nets
Kamila Barylska Reversible Computations vs Reversibility
Piotr Faliszewski Robustness Among Multiwinner Rules
Damian Kurpiewski Fixpoint Approximation of Strategic Abilities under Imperfect Information
Tomasz Michalak Strategic Social Network Analysis
17:00
Break
19:00
Conference dinner in the garden
10:00
Invited talk: Piotr Indyk
Beyond P vs. NP: Quadratic-Time Hardness For Big Data Problems
The theory of NP-hardness has been very successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make them run for days, weeks or more. For example, quadratic time algorithms, although practical on moderately sized inputs, can become inefficient on big data problems that involve gigabytes or more of data. Although for many problems no sub-quadratic time algorithms are known, any evidence of quadratic-time hardness has remained elusive.
In this talk I will give an overview of recent research that aims to remedy this situation. In particular, I will describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., Support Vector Machines or gradient computation in neural networks). All of them have polynomial time algorithms, but despite extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.

11:00
Coffee break
11:30
Contributed talks - session #3
Stefan Dziembowski Proofs of Space
Marcin Waniek Hiding Relationships in a Social Network
Mateusz Miotk New operation to create Bipartite Graphs
Jadwiga Sosnowska Attachment Centrality for Weighted Graphs
Oskar Skibski Axiomatic Approach to Centrality Measures
Eryk Kopczyński Hyperbolic triangular grids and discrete hyperbolic random graphs
13:00
Lunch
14:00
Invited talk: Michał Skrzypczak
Deciding complexity of languages via games
My presentation is about effective characterisations: given a representation of a regular language, decide if the language is ``simple'' in some specific sense. A classical example of such a characterisation is the result by Schutzenberger, McNaughton and Papert, saying that it is decidable if a given regular language of finite words can be defined in first-order logic. Over the years, such characterisations were provided for many other natural classes of languages, especially in the case of finite and infinite words.
The aim of my presentation is to survey a number of examples in which the characterisation can be obtained by a well-designed game of infinite duration. A simple and nice instance of such a situation is when one relates the deterministic index hierarchy with the topological complexity of languages of infinite words (i.e. Wagner vs. Wadge hierarchy). During the talk I will present some resent results obtained using that game-based technique.

15:00
Coffee break
15:30
Contributed talks - session #4
Paweł Urzyczyn Answer Set Programming in Intuitionistic Logic
Aleksy Schubert Coq Support in HAHA
Michał Wrona The Complexity of Minimal Inference Problem for Conservative Constraint Languages
Mikolaj Bojańczyk On a probabilistic variant of MSO
Paweł Parys Recursion Schemes and the WMSO+U Logic
16:45
Closing

Registration info

Registration site: http://fit2017.mimuw.edu.pl/register

To participate in FIT 2017, you need to register by June 18, 2017 June 28, 2017.

The conference fee is 215 PLN. Your payment must be completed by June 30, 2017.

Students and faculty affiliated with the University of Warsaw will be paid automatically via an internal transfer.

The FIT 2017 fee covers:

  • participation in all sessions and invited talks of FIT 2017,
  • conference dinner on Friday (July 7), held in the UW Library garden, and
  • lunches on Friday and Saturday and coffee breaks.

Note: The conference fee does not cover accommodation.

Participants (61)

Łukasz Kowalik (University of Warsaw),
Karol Żebrowski (University of Warsaw),
Emirhan Gürpınar (University of Warsaw, ENS Lyon),
Jakub Szymanik (University of Amsterdam),
Stefan DziembowskiTALK (University of Warsaw),
Piotr Sankowski (University of Warsaw),
Pierre Pradic (University of Warsaw),
Tomasz Gogacz (University of Warsaw),
Szymon Toruńczyk (University of Warsaw),
Marcin Przybyłko (University of Warsaw, University of New Caledonia),
Jan MarcinkowskiTALK (University of Wroclaw),
Adam Witkowski (University of Warsaw),
Marcin WaniekTALK (University of Warsaw),
Jacek Chrząszcz (University of Warsaw),
Daria Walukiewicz-Chrząszcz (University of Warsaw),
Damian Niwinski (University of Warsaw),
Nils Vortmeier (TU Dortmund University),
Konstanty Junosza-SzaniawskiTALK (Warsaw University of Technology),
Piotr Danilewski (Jagiellonian University),
Dorota Celińska (University of Warsaw),
Eryk KopczyńskiTALK (University of Warsaw),
Lorenzo Clemente (University of Warsaw),
Bruno Guillon (Università degli Studi di Milano),
Aleksy SchubertTALK (University of Warsaw),
Laure Daviaud (University of Warsaw),
Filip Murlak (University of Warsaw),
Thomas Zeume (University of Warsaw),
Mateusz Łącki (University of Warsaw),
Tomasz MichalakTALK (University of Warsaw),
Agnieszka MykowieckaTALK (University of Warsaw),
Krzysztof RządcaTALK (University of Warsaw),
Arkadiusz SocałaTALK (University of Warsaw),
Piotr FaliszewskiTALK (AGH University of Science and Technology),
Daniel Malinowski (University of Warsaw),
Damian KurpiewskiTALK (Polish Academy of Sciences),
Vincent Penelle (University of Warsaw),
Jarosław PaszekTALK (University of Warsaw),
Jakub Michaliszyn (University of Wroclaw),
Marcin PilipczukTALK (University of Warsaw),
Piotr Wieczorek (University of Wroclaw),
Linh Nguyen (University of Warsaw),
Anna Gambin (University of Warsaw),
Michał Kutwin (University of Warsaw),
Paweł Idziak (Jagiellonian University),
Grzegorz Stachowiak (University of Wroclaw),
Radosław Ziemann (University of Gdansk),
Michał WronaTALK (Jagiellonian University),
Rafał Witkowski (Adam Mickiewicz University in Poznan),
Paweł UrzyczynTALK (University of Warsaw),
Paweł ParysTALK (University of Warsaw),
Anna GogolińskaTALK (Nicolaus Copernicus University),
Mateusz MiotkTALK (University of Gdansk),
Adam Doliwa (University of Warmia and Mazury in Olsztyn),
Kamila BarylskaTALK (Nicolaus Copernicus University),
Leszek Pacholski (University of Wroclaw),
Michał Skrzypczak (University of Warsaw),
Michał Pilipczuk (University of Warsaw),
Andrzej Tarlecki (University of Warsaw),
Mikolaj BojanczykTALK (University of Warsaw),
Jadwiga SosnowskaTALK (University of Warsaw),
Oskar SkibskiTALK (University of Warsaw),



Organizing committee

Organizers

Contact

E-mail: fit2017@mimuw.edu.pl
Wydział Matematyki, Informatyki i Mechaniki
Uniwersytet Warszawski
Banacha 2
02-097 Warszawa

Send a message