Seminaria

25.04.2017 14:15
Michał Ziobro
Kryptologia
Introduction to Homomorphic Encryption
26.04.2017 12:15
Konrad Kalita
Podstawy Informatyki
Java Generics are Turing Complete by Radu Grigore
This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by
Kennedy and Pierce in 2007. It also follows that Java’s type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser
generator for fluent interfaces.
26.04.2017 16:15
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: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778.

27.04.2017 16:15
Jakub Szarawski
Optymalizacja Kombinatoryczna
A greedy approach to the Turtle Tower problem
In the Turtle Tower problem we are given n turtles with a mass and capacity for each of them. We are looking for the highest tower possible, regarding that capacity of every turtle in the tower cannot be exeeded by the sum of the masses of turles it carry. Presented solution is faster than commonly known dynamic one.
04.05.2017 16:15
Grzegorz Bukowiec
Optymalizacja Kombinatoryczna
Even factors of graphs
10.05.2017 16:15
Torsten Ueckerdt
Karlsruhe Institute of Technology
Informatyka Teoretyczna
The k-Strong Induced Arboricity of a Graph

Motivated by a connection to vertex-distinguishing colorings, we initiate the study of a new graph covering parameters: The k-strong induced arboricity. For a graph G and a positive integer k, a k-strong induced forest F in G is an induced forest in which every component has at least k edges. An edge in G is called k-valid if it is contained in at least one k-strong induced forest. The k-strong induced arboricity fk(G) is the smallest number m such that all k-valid edges of G can be covered with m k-strong induced forests in G.

We demonstrate that the k-strong induced arboricity is not monotone, neither in k, nor under taking subgraphs or even induced subgraphs. In particular we construct 2-degenerate graphs G with fk(G)
3 and fk+1(G) arbitrarily large. Focusing on the supremum fk(C) of fk(G) among all graphs G from a given graph class C, we prove that fk(G) is finite whenever C is of bounded expansion. For the class C of planar graphs we prove that fk(C) is 8,9 or 10. Moreover we give necessary and sufficient conditions for f1(C) to be finite in terms of r-shallow minors of graphs in C, a notion recently introduced by Nešetřil and Ossona de Mendez.

This is based on joint work with Maria Axenovich, Philip Dörr, Daniel Gonçalves, and Jonathan Rollin.

11.05.2017 16:15
Anna Kobak
Optymalizacja Kombinatoryczna
Lambda number for the direct product of some family of graphs
17.05.2017 12:15
Jakub Nowak
Podstawy Informatyki
Generic Complexity of Presburger Arithmetic by Alexander N. Rybalov
Fischer and Rabin proved in that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and nondeterministic Turing machines). In paper 4  a theory of generic-case complexity was developed, where algorithmic problems are studied on "most" inputs instead of set of all inputs. An interesting question rises about existing of more efcient (say, polynomial) generic algorithm deciding Presburger Arithmetic on some set of closed formulas of
asymptotic density 1 (so-called generic set). We prove, however, that there is not even an exponential generic algorithm working correctly on a set of inputs which (so-called strongly generic set).
18.05.2017 16:15
Katrzyna Janocha
Optymalizacja Kombinatoryczna
Proper Orientations of Planar Bipartite Graphs
24.05.2017 12:15
Piotr Wójcik
Podstawy Informatyki
Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and Applications by O.Bodini, J. David, and Ph. Marchal
In this paper, we redesign and simplify an algorithm due to Remy et al. for the generation of rooted planar trees that satisfies a given partition of degrees. This new version is now optimal in terms of
random bit complexity, up to a multiplicative constant. We then apply a natural process “simulate-guess-and-proof” to analyze the height of a random Motzkin in function of its frequency of unary nodes. When the number of unary nodes dominates, we prove some unconventional height
phenomenon.
31.05.2017 12:15
Grzegorz Bukowiec
Podstawy Informatyki
The Undecidability of the Generalized Collatz Problem by Stuart A. Kurtz and Janos Simon
The Collatz problem, widely known as the 3x + 1 problem, asks whether or not a certain simple iterative process halts on all inputs. In this paper, we build on work of J. H. Conway to show that a natural generalization of the Collatz problem is $PI^0_2$ complete.
31.05.2017 16:15
Piotr Micek
Informatyka Teoretyczna
Ramsey Theory for Binary Trees and the Separation of Tree-chromatic Number from Path-chromatic Number

We propose a Ramsey theory for binary trees and prove that for every r-coloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have tree-chromatic number at most 2 while the path-chromatic number is bounded. This construction resolves a problem posed by Seymour.

Joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter.

14.06.2017 16:15
Piotr Wójcik
Informatyka Teoretyczna
On the asymptotic density of valid sentences in first-order logic about one binary relation

This study arises from the following question: what is the proportion of tautologies of the given length n among the number of all FO relational sentences of length n? We investigate the simplest language with a fixed signature σ = {r}, where r is a binary relation symbol. The model with four logic symbols and an universal quantifier lead us to discover an unexpected result - the fraction of valid sentences is always greater than a fixed constant and therefore the density, if exists, is positive. The main theorem is derived from the analysis of structural properties of FO formulae, which themselves bear strict resemblance to structural properties of λ-terms.

Poprzednie referaty

20.04.2017 16:15
Helena Borak, Zygmunt Łenyk
Optymalizacja Kombinatoryczna
Necklaces, Convolutions, and X + Y, A new upper bound for the online square packing
Necklaces, Convolutions, and X + Y

The necklace alignment problem is to find the optimal rotation of the necklaces to best align the beads, when we have two necklaces given, each with n beads at arbitrary positions. Alignment is measured according to the ℓ_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = ∞ and how these problems can be reduced to convolution problems which can be solve in subquadratic time. Besides, we say how the necklace alignment problems, and their corresponding convolution problems, are also intrinsically connected to problems on X + Y matrices.

A new upper bound for the online square packing

In online square packing problem we try to minimise the height of squares on a plane with width 1. Squares come one by one, they can’t overlap and once set, it’s position can’t be changed. A new upper bound (ratio between algorithm result and optimal packing) is found by applying modified version of previously used First Fit Shelf algorithm.
19.04.2017 16:15
Lech Duraj, Adam Polak
Informatyka Teoretyczna
Longest Common Strictly Increasing Subsequecnce

The Longest Common Increasing Subsequence problem is a variant of classic Longest Common Subsequence problem, which can be solved in quadratic time with a simple dynamic programming algorithm. During the talk we will show a reduction from the Orthogonal Vectors problem to the Longest Common Increasing Subsequence problem which proves that the latter cannot be solved in strongly subquadratic time unless the SETH is false.

 

Simple modifications of the reduction prove that the problem for k sequences cannot be solved in O(nk-ε) time, that the same lower bounds apply to the Longest Common Weakly Increasing Subsequence, and that the assumption of SETH can be replaced with a weaker statement about satisfiability of non-deterministic branching programs.

12.04.2017 12:15
Jarek Duda
Podstawy Informatyki
Boundaries for hashing problem, or how many bits ones individuality costs
I will talk about information-theoretic boundaries for the hashing problem, the Bloom filter, and generally about informational content of structures like trees and graphs. While the label size has to grow like logarithm of the population size, neglecting information about the order (lg(n!) bits), we get a linear growth of entropy of population, allowing to bound 'the cost of individuality' asymptotically to ~2.33275 bits per object.
06.04.2017 16:15
Andrzej Głuszyński, Jakub Nowak
Optymalizacja Kombinatoryczna
Local Antimagic Vertex Coloring of a Graph, A short proof of Cayley's tree formula
Local Antimagic Vertex Coloring of a Graph

The edge labelling is called 'local antimagic', if for all vertices sum of labels for incident edges is different for every two adjacent vertices. Such sum induce a correct vertex colouring. The local antimagic chromatic number - X_la(G) - is the minimum number of colours used by any proper local antimagic labelling. In the paper authors present results on this parameter for trees, friendship, wheel and clique graphs.


A short proof of Cayley's tree formula

Cayley’s tree formula is a very elegant result in Graph Theory. The problem is to find the number of all possible trees on a given set of labeled vertices. For n = 2 and vertex set {v1, v2}, we have only one tree. For n = 3 and vertex set {v1, v2, v3}, we have 3 different trees. Similarly for n = 4, we have 16 trees. We give a short proof of Cayley’s tree formula for counting the number of different labeled trees on n vertices.

Alok Bhushan Shukla, A short proof of Cayley's tree formula.
05.04.2017 12:15
Szymon Stankiewicz
Podstawy Informatyki
CANTOR POLYNOMIALS AND THE FUETER-POLYA THEOREM by MELVYN NATHANSON

A packing polynomial is a polynomial that maps the set N^2 of lattice points with nonnegative coordinates bijectively onto N. Cantor constructed two quadratic packing polynomials, and Fueter and Polya proved analytically that the Cantor polynomials are the only quadratic packing polynomials.
The purpose of this paper is to present a beautiful elementary proof of Vsemirnov of the Fueter-Polya theorem. It is a century-old conjecture that the Cantor polynomials are the only packing polynomials on N^2.

04.04.2017 14:15
Mateusz Jachna
Kryptologia
Secure Hash Algorithms family and the recently found collision for SHA-1
28.03.2017 14:15
Piotr Wójcik
Kryptologia
Quantum Authentication with Key Recycling

We show that a family of quantum authentication protocols introduced in FOCS 2002 can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all non-recycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource.

References:

[1] Christopher Portmann, Quantum Authentication with Key Recycling (pdf)

23.03.2017 16:15
Aleksandra Mędrek, Marcin Muszalski
Optymalizacja Kombinatoryczna
Planning for Fast Connectivity Updates
Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d > 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
  1. Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007
21.03.2017 14:15
Jan Szczepaniec
Kryptologia
Inclusive Block Chain Protocols

Distributed cryptographic protocols such as Bitcoin and Ethereum use the block chain to synchronize a global log of events between nodes in their network. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly.
Inclusive Block Chain Protocol is a alternative structure consists of a directed acyclic graph of blocks to the chain that allows for operation at much higher rates. It is showed that with this system the advantage of highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks.


References:
[1] Lewenberg Y., Sompolinsky Y., Zohar A., Inclusive Block Chain Protocols. In: Böhme R., Okamoto T. (eds) Financial Cryptography and Data Security, 2015. Lecture Notes in Computer Science, vol 8975. Springer, Berlin, Heidelberg (pdf)

16.03.2017 16:15
Patryk Urbański
Optymalizacja Kombinatoryczna
Generating Linear Extensions Fast

One of the most important sets associated with a poset P is its set of linear extensions, E(P). In this paper, we present an algorithm to generate all of the linear extensions of a poset in constant amortized time; that is, in time O(e(P)), where e(P) = |E(P)|. The fastest previously known algorithm for generating the linear extensions of a poset runs in time O(n*e(P)), where n is the number of elements of the poset. Our algorithm is the first constant amortized time algorithm for generating a ``naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furthermore, we show that linear extensions can be generated in constant amortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to efficiently count linear extensions, and to compute P(x < y), for all pairs x,y, in time O(n^2 + e(P)).

Gara Pruesse, Frank Ruskey. Generating Linear Extensions Fast. SIAM J. Comput. Vol. 23, No. 2 (1994), pp. 373-386.

16.03.2017 14:15
Jakub Cisło, Grzegorz Jurdziński
Algorytmika
Tight Hardness Results for LCS and other Sequence Similarity Measures
15.03.2017 16:15
Manuel Bodirsky
TU Dresden
Informatyka Teoretyczna
The tractability conjecture for finitely bounded homogeneous structures
Finitely bounded homogeneous structures form a large class of infinite structures that can be seen as a generalisation of the class of all finite structures. Many results about finite structures, in particular in the context of the complexity of constraint satisfaction problems, can be generalised to this larger class. In this talk I will present a reformulation of a tractability conjecture for CSPs for this class in terms of polymorphisms, due to Barto and Pinsker (LICS 2016), and I will present a proof that the condition given in the tractability conjecture is decidable (under some Ramsey-theoretic assumptions that might hold in general for all reducts of finitely bounded homogeneous structures).
15.03.2017 12:15
Łukasz Lachowski
Podstawy Informatyki
Impossibility of Distributed Consensus with One Faulty Process by MICHAEL J. FISCHER, NANCY A. LYNCH AND MICHAEL S. PATERSO
The consensus problem involves a asynchronous system of processes, some of which may be unreliable.The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
14.03.2017 14:15
Marcin Briański
Kryptologia
Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

The talk is based on the paper with the same title by Rosario Gennaro, Craig Gentry and Bryan Parno.

Verifiable Computation enables a computationally weak client to "outsource" the computation of a function F on various inputs x1, ..., xk to one or more workers. The workers return the result of the function evaluation, e.g., yi = F(xi), as well as a proof that the computation of F was carried out correctly on the given value xi. The verification of the proof should require substantially less computational effort than computing F(xi) from scratch.

We present a protocol that allows the worker to return a computationally sound, non-interactive proof that can be verified in O(m) time, where m is the bit-length of the output of F. The protocol requires a one-time pre-processing stage by the client which takes O(|C|) time, where C is the smallest Boolean circuit computing F. Our scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the values xi or yi.

09.03.2017 16:15
Grzegorz Matecki
Optymalizacja Kombinatoryczna
Boolean dimension of posets
A boolean dimension bdim(P) of a poset P=(X,<) is a smallest number k for which there is a set l1, l2, ..., lk of labelings X:->N and a boolean formula f(a1, ..., ak) such that the following is true: x < y in P iff f(a1, .., a_k) = 1 where ai =1 iff li(x) < li(x).
Generally, it is simple to observe that bdim(P) <= dim(P). Also, it is known that there is a constant c such that bdim(n) <= c log(n) for any poset P of size n.
The are few interesting open problems for boolean dimension:
1) Is boolean dimension of the boolean lattice of size n less that n?
2) Is there a constant c such that bdim(P) < c for any planar poset P?
 
09.03.2017 14:00
Sylwester Klocek, Wojciech Kruk
Algorytmika
The Alternating Stock Size Problem and the Gasoline Puzzle
08.03.2017 12:15
Maciej Bendkowski
Podstawy Informatyki
Boltzmann samplers: random generation of combinatorial structures with an application to lambda calculus
In their seminal paper, Duchon et al. proposed a surprisingly simple, general-purpose framework of Boltzmann samplers meant for random generation of combinatorial structures. In this talk we revisit their method and discuss its elegant relation with analytic combinatorics as well as important practical implementation details. Finally, we discuss the application of Boltzmann samplers to the random generation of lambda terms used, e.g. in testing functional programming compilers.
07.03.2017 14:15
Zygmunt Łenyk
Kryptologia
Speeding up modular multiplication using Montgomery and Barrett reduction
In the talk we present Montgomery and Barrett reductions that are used to speed up modular computations. In both reductions some pre-computations are made allowing for replacing subsequent expensive divisions by some fixed modulus with much cheaper operations involving a suitable power of 2. This is particularly useful when many modular divisions by the same modulus are performed (for example in finite field arithmetic or in RSA).
07.03.2017 14:15
Mateusz Twaróg, Łukasz Majcher
Optymalizacja Kombinatoryczna
Combinatorial library core
Presentation and discussion on core functionalities of the c++ combinatorial library. introduction to classes representing graphs, graph traversing algorithm templates and simple GUI.
01.03.2017 12:15
Michał Zwonek
Podstawy Informatyki
Wielomianowe kodowania

Rozważany będzie problem istnienia wielomianowej bijekcji, najniższego stopnia, między N^k, a N. Przedstawione będą także problemy otwarte związane z tą tematyką.

Materiały do wystąpienia:

1) Elementarny dowód Twierdzenie Feuter-Polya (jedyny kwadratowy i bijektywny wielomian N^2->N to funkcja cantore'a) https://arxiv.org/abs/1512.08261

2) Praca, w której autorzy pokazują nieistnienie wielomianów 3 i 4 stopnia.  http://www.sciencedirect.com/science/article/pii/0022314X78900367

3) Praca podobnie tematyczna odnosząca się do problemu istnienia wielomianów bijektywnych z pewnego sektora N^2 w N. (To o czym wspomniałem na koniec, opis tego problemu jest też pod koniec w 1) ). Pod koniec pracy jest opisane 6 problemów otwartych związanych z tą tematyką. https://arxiv.org/abs/1305.2538

4) W podobnej tematyce. http://www.sciencedirect.com/science/article/pii/0022314X78900355
 

 

28.02.2017
Michał Dyrek
Kryptologia
LLL algorithm and its applications in Number Theory and Cryptography
The talk is devoted to the algorithm by A. Lenstra, H. Lenstra and L. Lovász dated 1982 allowing for approximation of Shortest Vector Problem in polynomial time. We will present the idea of the algorithm and highlight its applications such as factoring polynomials over Q, constructing polynomials with small coefficients and connections with attacks on RSA.
26.01.2017 16:15
Wojciech Kruk, Maciej Woźniak
Optymalizacja Kombinatoryczna
A few open problems
We mentioned the following open problems in graph theory and discrepancy theory:

1. Erdos discrepancy problem
2. Hoang - Reed conjecture
3. Seagull problem - a consequence of Hadwiger's conjecture
25.01.2017 16:15
01.03.2017 16:15
Grzegorz Guśpiel
Informatyka Teoretyczna
Partial Visibility Representation Extension Problem

We study a class of graphs that have a special geometric representation. By a bar visibility representation of an undirected graph we mean a function that associates with each vertex of a graph a horizontal line segment in such a way, that between segments representing two ends of an edge there is a vertical strip (of visibility). In case of directed graphs, we additionally assume that the visibility is from the bottom to the top, that is the line segment representing the source of the edge is below the one for the target.

Graphs admitting such representations are well understood and can be recognized in linear time, both in the undirected and in the directed case. We work in a more subtle setting, where line segments are already associated with some vertices of a graph, and the question is if this can be extended to a bar visibility representation of an entire graph. We prove some results on complexity of this kind of problems.

This is joint work with Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk and Giuseppe Liotta. The manuscript is available here: https://arxiv.org/abs/1512.00174

25.01.2017 12:00
Sylwester Klocek
Podstawy Informatyki
Incompleteness, Undecidability and Automated Proofs by Cristian S. Calude and Declan Thompson
Incompleteness and undecidability have been used for many years as arguments against automatising the practice of mathematics. The advent of powerful computers and proof-assistants – programs that assist the development of formal proofs by human-machine collaboration – has revived the interest in formal proofs and diminished considerably the value of these arguments. In this paper we discuss some challenges proof-assistants face in handling undecidable problems – the very results cited above – using for illustrations the generic proof-assistant Isabelle.
24.01.2017
Kamil Sałaś
Kryptologia
Lower Bounds for Discrete Logarithms
In the talk we will present the computational complexity of the discrete logarithm in the context of "generic algorithms", that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as unique binary string. For discrete logarithm, any generic algorithm must perform Ω(p^1/2) group operations, where p is the largest prime dividing the order of the group.
19.01.2017
Paweł Petecki
Akademia Górniczo-Hutnicza
Optymalizacja Kombinatoryczna
Symmetry breaking polynomial
Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetry-breaking if for every non-identity automorphism φ in Γ, there is some vertex v of G such that c(v)≠c(φ(v)). There has been a lot of work on the minimum number of colors in a symmetry-breaking coloring of G. We discuss here a different problem: counting the number of k-colorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial ψG. For positive integer k (number of colors), ψG(k) is the number of k-colorings that break all non-trivial symmetries of the graph G.
18.01.2017 16:15
Marian Mrozek
Informatyka Teoretyczna
The discrete charm of Morse theory
The lecture will start with recalling P.S. Alexandroff's Theorem (1937) on mutual equivalence of posets and T0 topologies on finite sets. Next, we will outline the combinatorial version of the classical Morse Theory presented by R. Forman in 1998. Then, we will elaborate Forman's ideas towards the combinatorial topological dynamics with potential applications in Big Data problems and time series. The topics of the lecture will be expanded in a course for PhD students in the summer semester 2016/17.
18.01.2017 12:00
Michał Ziobro
Podstawy Informatyki
Inhabitation in Simply-Typed Lambda-Calculus through a Lambda-Calculus for Proof Search by Jose Espırito Santo, Ralph Matthes, Luıs Pinto
Kontynuacja seminarium z 23.11.2016
17.01.2017
Grzegorz Bukowiec
Kryptologia
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

Until recently, all the algorithms for computing discrete logarithm had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasi-polynomial complexity for discrete logarithm in finite fields of small characteristic and that even for other cases still surpasses the Function Field Sieve method.

References:

[1] R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf)

11.01.2017 16:15
Patryk Mikos
Informatyka Teoretyczna
Online coloring of intervals with bandwidth
We study the online interval coloring problem with bandwidth. The input is a sequence of pairs Ji= (Ii,wi) where Ii is an interval on the real line and wi is a real number from (0,1]. In this setting a proper coloring is a function f:Ji →N such that for each color c and any point p on the real line, the sum of bandwidths of intervals containing p and colored by c does not exceed 1. The best known lower bound on the competitive ratio in this problem is 24/7. We present an explicit strategy for Presenter that increases the competitive ratio ifor this problem to at least 4.1626.
11.01.2017 12:00
Patryk Mikos
Podstawy Informatyki
ON THE NUMBER OF DISTINCT LANGUAGES ACCEPTED BY FINITE AUTOMATA WITH n STATES by Michael Domaratzki, Derek Kisman and Jeffrey Shallit
We give asymptotic estimates and some explicit computations for both the number of distinct languages and the number of distinct finite languages over a k-letter alphabet that are accepted by deterministic finite automata (resp. nondeterministic finite automata) with n states.
10.01.2017
Szymon Policht
Kryptologia
Faster operations on elliptic curves using Edwards curves
Elliptic curve cryptography is a broad and commonly used section of modern-day cryptography. Because of that, the speed of elliptic curve operations directly impacts the performance of many current systems. In this talk we'll show how to speed up those operations using Edwards curves.

References:
[1] Bernstein D.J., Lange T. (2007) Faster Addition and Doubling on Elliptic Curves. In: Kurosawa K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg (https://eprint.iacr.org/2007/286.pdf)
05.01.2017 14:15
Jan Derbisz, Jakub Łabaj
Algorytmika
Sortowanie przez spacer po drzewie

Rozważamy następujący problem: wierzchołki drzewa ponumerowane są kolejnymi liczbami naturalnymi, a dodatkowo w wierzchołku x leży skrzynka o numerze p(x), przy czym funkcja p jest permutacją zbioru {1,2,..,n}. Rozważamy chodzącego po drzewie robota, który może w danym momencie trzymać tylko jedną skrzynkę, może też podnieść napotkaną skrzynkę upuszczając aktualnie trzymaną. Celem robota jest posortować skrzynki (przenosząc każdą do wierzchołka o odpowiednim numerze), przechodząc po drzewie najkrótszą możliwą ścieżką. Praca D. Grafa podaje algorytm znajdujący taką ścieżkę w czasie O(n2) oraz dowód, że jeśli drzewo zastąpimy grafem planarnym, problem staje się NP-zupełny.

04.01.2017 12:00
Konrad Kalita
Podstawy Informatyki
ANALYTIC MODELS AND AMBIGUITY OF CONTEXT-FREE LANGUAGES by Philippe Flajolet
We establish that several classical context-free languages are inherently ambiguous by proving that their counting generating functions, when considered as analytic functions, exhibit some characteristic form of transcendental behaviour. To that purpose, we survey some general results on elementary analytic properties and enumerative uses of algebraic functions in relation to formal languages In particular, the paper contains a general density theorem for unambiguous context-free languages.
03.01.2017

Kryptologia
(Cancelled)
22.12.2016 16:15
Łukasz Majcher, Jan Szczepaniec
Optymalizacja Kombinatoryczna
Convex p-partitions of bipartite graphs
A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
21.12.2016 16:15
Maciej Bendkowski
Informatyka Teoretyczna
Boltzmann samplers: a framework for random generation of combinatorial structures with an application to lambda calculus
In their seminal paper, Duchon et al. proposed a surprisingly simple, general-purpose framework of Boltzmann samplers meant for random generation of combinatorial structures. In this talk we revisit their method and discuss its elegant relation with analytic combinatorics as well as important practical implementation details. Finally, we discuss the application of Boltzmann samplers to the random generation of lambda terms used, e.g. in testing functional programming compilers.
20.12.2016 12:00
Bartłomiej Puget
Kryptologia
An introduction to quantum computing and cryptography II
15.12.2016 14:15
Michał Glapa, Franciszek Stokowacki
Algorytmika
Skojarzenia w grafach metodami algebraicznymi
Na seminarium omówiony zostanie przełomowa praca z 2006, autorstwa Muchy i Sankowskiego, opisująca algorytm obliczania skojarzeń w grafach za pomocą eliminacji Gaussa. Przedstawiony algorytm ma złożoność zależną od mnożenia macierzy, niższą niż O(n2.5), algorytmu Micaliego-Vaziraniego, który bardzo długo był najlepszą znaną metodą.
15.12.2016
Anna Kobak
Optymalizacja Kombinatoryczna
Open problems in graph theory concerning minors.
We mentioned following open problems in graph theory:
  1. Hadwiger's Conjecture
  2. Seagull Conjecture
  3. Jorgensen's Conjecture
  4. Unfriendly partitions
  5. and a few more conjectures concerning minors.
14.12.2016 16:15
Grzegorz Matecki
Informatyka Teoretyczna
Two-Dimensional Irregular Packing Problem
We present results on packing irregular shapes onto given sheets of material.
14.12.2016 12:00
Piotr Wójcik
Podstawy Informatyki
Enumeration and random generation of accessible automata by Frederique Bassino and Cyril Nicaud
We present a bijection between the A_n of deterministic and accessible automata with n states on a k-letters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn + 1 elements into n non-empty subsets. This combinatorial construction shows that the asymptotic order of the cardinality of A_n is related to the Stirling number. Our bijective approach also yields an efficient random sampler, for the uniform distribution, of automata with n states, its complexity is O(n^3/2), using the framework of Boltzmann samplers.
13.12.2016 12:00
Krzysztof Kleiner
Kryptologia
An introduction to quantum computing and cryptography I

In this talk we're going to discuss quantum informatics and its impact on the field of cryptography. We will introduce the basic concepts of quantum computing as well as cryptography based on Quantum Key Distribution scheme, one of the aspects of quantum informatics which already is being used in practice. Then we will present Shor's algorithm for polynomial-time factorization, responsible for the cryptosystems based on the hardness of factorization or discrete logarithm (in abelian groups) being no longer secure against an adversary with access to a quantum computer.


References:

[1] M. Hirvensalo, Quantum Computing (http://link.springer.com/book/10.1007/978-3-662-09636-9)
[2] F. Benatti, M. Fannes, R. Floreanini, D. Petritis, Quantum Information, Computation and Cryptography (http://link.springer.com/book/10.1007/978-3-642-11914-9)
[3] D. Deutsc, Lectures on Quantum Computation (http://www.daviddeutsch.org.uk/videos/)
[4] U. Vazirani, BerkeleyX's Lectures: Quantum Mechanics and Quantum Computation (https://www.edx.org/course/quantum-mechanics-quantum-computation-uc-berkeleyx-cs-191x)

08.12.2016
Lech Duraj
Algorytmika
Krótka opowieść o mnożeniu macierzy

W ostatnich latach pojawiają się kolejne, coraz lepsze algorytmy mnożenia macierzy. Każdy z nich jest jednak tylko nieznacznie szybszy od poprzednich, będąc przy tym nierównie trudniejszy w zrozumieniu i analizie. Fakt ten jeszcze bardziej komplikuje otwarte od wielu lat pytanie o złożoność optymalnego algorytmu mnożenia macierzy.

Celem prezentacji jest krótkie omówienie technik używanych do ataków na ten niezwykle ważny i trudny problem. Prezentacja oparta jest na przeglądowym wykładzie François Le Galla (autora ostatnich wyników w tym temacie) z 2014 roku.

08.12.2016
Zygmunt Łenyk
Optymalizacja Kombinatoryczna
Rendezvous on the line.
This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. In line case, players are placed on the line with distance 2, without knowing neither on which side is their partner, nor the direction of the line. I'll concentrate on the symmetric case where players must follow a specific (but maybe mixed) strategy. The conjecture is that best expected time of meeting two players equals 4.25.
  1.  
  2.  
  3. www.openproblemgarden.org/op/rendezvous_on_a_line
  4. Improved bounds for the symmetric rendezvous value on the line. Qiaoming Han, Donglei Du, Juan Vera, Luis F. Zuluaga. SODA 2007
07.12.2016 12:00
Jakub Brzeski
Podstawy Informatyki
ENUMERATION OF FORMAL LANGUAGES by Michael Domaratzki
We survey recent results on the enumeration of formal languages. In particular, we consider enumeration of regular languages accepted by deterministic
and nondeterministic finite automata with n states, regular languages generated by regular expressions of a fixed length, and !-regular languages accepted by Müller automata. We also survey the uncomputability of enumeration of context-free languages and more general structures.
06.12.2016
Marek Rusinowski
Kryptologia
Security of instant messaging applications.
Nowadays billions of people around the world are sharing sensitive information using instant messaging applications. We will look into the current state of IM security, the problems in this area and a few encryption protocols---OTR and Signal Protocol in particular---that provide security features desired by users.
01.12.2016
Aleksandra Mędrek, Krzysztof Maziarz
Algorytmika
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Praca Aleksandra Mądrego opisuje nowe podejście do problemu maksymalnego przepływu, z użyciem tzw. przepływów elektrycznych. W tej technice krawędziom przypisywany jest opór, a zadaniem jest zminimalizowanie wydzielonej energii. Dowolną sieć przepływową można zredukować do zadania przepływu elektrycznego, z użyciem pośredniej redukcji poprzez warianty problemu skojarzenia w grafie dwudzielnym. Głównym rezultatem pracy jest algorytm przepływu o złożoności O(m10/7), na seminarium będzie prezentowana prostsza wersja algorytmu, działająca w O(m3/2).

01.12.2016
Patryk Urbański
Optymalizacja Kombinatoryczna
Coloring Ordinary Maps, Maps of Empires and Maps of the Moon
A short review of generalized map coloring problems:
  • Heawood's empire coloring problem in the plane - 6M colors are sufficient to color a map of empires each consisting of at most M connected regions.
  • Earth-Moon map coloring Mathematics Magazine Vol. 66, No. 4 (Oct., 1993), pp. 211-226problem - it is known that the chromatic number of thickness-2 graphs is between 9 and 12. It is an open problem to find the exact value.
Coloring Ordinary Maps, Maps of Emipres, and Maps of the Moon. Joan P. Hutchinson. Mathematics Magazine. Vol. 66, No. 4 (Oct., 1993), pp. 211-226.
01.12.2016
Mateusz Twaróg
Optymalizacja Kombinatoryczna
Second Neighborhood via First Neighborhood in Digraphs

Second Neighborhood via First Neighborhood in Digraphs. Guantao Chen, Jian Shen, Raphael Yuster. Annals of Combinatorics. June 2003, Volume 7, Issue 1, pp 15–20.

30.11.2016 18:15
Bartosz Walczak
Informatyka Teoretyczna
Coloring curves that cross a fixed curve
A class of graphs is χ-bounded if the chromatic number of all graphs in the class is bounded by some function of their clique number. String graphs are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are χ-bounded. In particular, it is known since 2012 that the class of all string graphs is not χ-bounded. We prove that for every integer t≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χ-bounded. This result is best possible in several aspects; for example, the upper bound t on the number of crossings with the fixed curve cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called k-quasi-planar topological graphs. This is joint work with Alexandre Rok.
30.11.2016 12:00
Yauheni Ananchuk
Podstawy Informatyki
ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS by ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI
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
29.11.2016
Anna Kobak
Kryptologia
Breaking RSA vs Factoring in generic ring model

In the talk we present results of Aggarwal and Maurer [1], who showed that a generic ring algorithm for breaking RSA with modulus $N$ can be converted into an algorithm for factoring $N$. The results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input modulo $N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

 

References:

[1] D. Aggarwal, U. Maurer, Breaking RSA Generically is Equivalent to Factoring, EUROCRYPT 2009

24.11.2016
Wojciech Łopata
Optymalizacja Kombinatoryczna
Several open problems from game theory, graph theory and combinatorics.

I'll briefly introduce the audience to two unrelated areas: book embedding and mechanism design, and walk through some open problems in those areas.
Wikipedia: Book embedding
Wikipedia: Mechanism design

24.11.2016
Dominika Salawa, Jakub Cisło
Algorytmika
Greedy algorithms for Steiner forest

Referowana praca rozstrzyga długo otwarty problem: czy budowanie drzewa Steinera zachłannym algorytmem daje wynik gorszy od optymalnego o stałą multiplikatywną? Autorzy (A. Gupta, A. Kumar) dowodzą, że tak, dla stałej równej 96. Jest to pierwsze znane oszacowanie wyniku algorytmu zachłannego, wcześniej podawane algorytmy aproksymacyjne dla tego problemu oparte były o programowanie liniowe.

23.11.2016
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.

23.11.2016
Michał Ziobro
Podstawy Informatyki
Inhabitation in Simply-Typed Lambda-Calculus through a Lambda-Calculus for Proof Search by Jos´e Espırito Santo, Ralph Matthes, Luıs Pinto
A new, comprehensive approach to inhabitation problems in simply-typed lambda-calculus is shown, dealing with both decision and counting problems. This approach works by exploiting a representation of the search space generated by a given inhabitation problem, which is in terms of a lambda-calculus for proof search that the authors developed recently. The representation may be seen as extending the Curry-Howard representation of proofs by lambda-terms, staying within the methods of lambda-calculus and type systems. Our methodology reveals inductive descriptions of the decision problems, driven by the syntax of the proof-search expressions, and the end products are simple, recursive decision procedures and counting functions.
22.11.2016
Aleksandra Nowak
Kryptologia
Lattice Cryptography and The Learning With Errors Problem
17.11.2016
Paweł Kubiak
Optymalizacja Kombinatoryczna
Succinct Data Structures
17.11.2016
Patryk Gołębiowski, Wojciech Kruk
Algorytmika
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
Tematem referatu jest praca Colina White'a dotycząca algorytmów poszukiwania ścieżki na grafach o szczególnym własnościach, mających w założeniu modelować rzeczywiste sieci dróg. Autor analizuje najpopularniejsze istniejące algorytmy i podaje dolne ograniczenia na ich złożoność.
16.11.2016
Bartłomiej Bosek
Informatyka Teoretyczna
Every digraph is majority 4-choosable
A majority coloring of a digraph is a coloring of its vertices such that for each vertex at most half of its out-neighbors has the same color as that vertex. A digraph D is majority k-choosable if for any assignment of color lists of size k to the vertices there is a majority coloring of D from these lists. We prove the statement in the title. This gives a positive answer to a question posed recently in 1. This is a joint work with Marcin Anholcer and Jarosław Grytczuk.
  1. S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colourings of Digraphs, Arxiv.
  2. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk Every digraph is majority 4-choosable, Arixv.
16.11.2016
Michał Zieliński
Podstawy Informatyki
Most programs stop quickly or never halt by Cristian S. Calude and Michael A. Stay
The aim of this paper is to provide a probabilistic, but non-quantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random N-bit program has halted by a random time.We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k >0, we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than 2^{−k}. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that “long” runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time 2^{N+constant} has effectively zero density.
15.11.2016
Piotr Kawałek
Kryptologia
Teoretyczne podstawy kryptoanalizy
Celem referatu jest przedstawienie teoretycznych modeli ataków kryptoanalitycznych oraz tematów pokrewnych wraz z przykładami.
10.11.2016
Magdalena Gargas, Mateusz Jachna
Algorytmika
Max flows in O(nm) time, or better
W pracy opisany jest nowy algorytm przepływu działający w czasie O(nm + m16/15 logn). Istotny jest fakt, że przez połączenie go z poprzednio znanymi algorytmami daje to pozytywną odpowiedź na pytanie, czy da się obliczyć maksymalny przepływ w czasie O(nm). Autorem pracy jest James B. Orlin.
10.11.2016
Grzegorz Bukowiec
Optymalizacja Kombinatoryczna
On more variants of the Majority Problem
09.11.2016
26.10.2016
Adam Polak
Informatyka Teoretyczna
Open problems in on-line and approximation algorithms
During the talk I will present several promising open problems including:
  • Online Deadline Scheduling with Machine Augmentation
  • Scheduling with Precedence Constraints
  • Multiway Cut
  • Traveling Repairman Problem
09.11.2016
Wojciech Kruk
Podstawy Informatyki
On the generic undecidability of the Halting Problem for normalized Turing machines by Alexander Rybalov
Hamkins and Miasnikov presented in 2004 a generic algorithm deciding the classical Halting Problem for Turing machines with one-way tape on a set of asymptotic probability one (on a so-called generic set). Rybalov in 2007 showed that there is no generic algorithm deciding this problem on strongly generic sets of inputs (some subclass of generic sets). In this paper we prove that there is no generic algorithm deciding the Halting Problem for normalized Turing machines on generic sets of inputs. Normalized Turing machines have programs with the following natural restriction: internal states with large indices
are not allowed at the beginning of the program. This condition does not reduce the class of computable functions because for every Turing machine there exists a normalized Turing machine which computes the same function. Our proof holds for machines with one-way and two-way tape. It also implies that the Hamkins-Miasnikov algorithm is not generic for normalized Turing machines.