During the seminar I will discuss a clever attack on RSA library used in Infineon chips. Researchers discovered that the prime factors used for constructing private keys have a peculiar form. This allowed them to use a modified version of Coppersmith algorithm to recover private key basing on their public counterpart in a reasonable time for keys up to 2048 bit long.

Dusan Klinec, Vashek Matyas, Matus Nemec, Marek Sys, Petr Svenda. The Return of Coppersmith’s A‚ack: Practical Factorization of Widely Used RSA Moduli.

Hackenbush is a two player game played on a graph with a few marked vertices. Players alternate turns. Each turn consists of removing one edge from the graph and all vertices that lost their connection to all marked ones. Player, that can't make a move, loses. I will present three different variants of Hackenbush(Red-Blue Hackenbush, Green Hackenbush and R-G-B Hackenbush) with methods to determine, which player has a winning strategy.

Padraic Bartlett. A Short Guide to Hackenbush. VIGRE REU 2006.

We define a method for edge coloring signed graphs and what it means for such a coloring to be proper. It then turns out that Vizing's Theorem is a special case of the more difficult theorem concerning signed graphs.

Richard Behr. Edge Coloring Signed Graphs. arXiv. 2018.

We will discuss variations of a zero sum game where one player writes down two numbers on cards. The second player learns one of the numbers to make a guess which of the numbers is larger. We will show variations of the game where the second player has a greater chance of winning than 1/2.

Alexander Gnedin. Guess the Larger Number. arXiv. 2016.

Jie Gao, Terrence Wong, Chun Wang, and Jia Yuan Yu. A Price-Based Iterative Double Auction for Charger Sharing Markets. arXiv. 2019.

For any graph G and positive integer p we can consider "exact distance graph" G in which vertices x and y are connected if and only if their distance in G is exactly p. We can bound chromatic number of such graphs using notion of weak coloring numbers. Proof becomes particularly valuable for odd p and planar graphs G.

Jan van den Heuvel, H.A. Kierstead, Daniel A. Quiroz. Chromatic Numbers of Exact Distance Graphs. arXiv, abs/1612.02160. 2016.

It's commonly known that planar graphs are at most 4-colorable. One possible direction towards determining when planar graphs can be 3-colorable is to narrow to particular planar graphs with enforced structure. For example, one can forbid cycles of length 4,5,...,k where k>=4. There is a conjecture of Steinberg from 1976, that planar graphs without cycles of length 4 and 5 (as subgraphs) are 3-colorable. It has been open problem till 2016, when it was disproved in joint paper of Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado, and we present proof from that paper.

Steinberg's Conjecture is false. Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado. arXiv, abs/1604.05108. 2016.

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.

During the seminar, we will discuss some open problems regarding the choosability number of planar graphs and related problems.

It is a known fact that Sperner's purely combinatorial lemma of triangulation is equivalent to theorems in the field of topology: Brouwer with a fixed point and Knastra-Kuratowski-Mazurkiewicz on covering the symplex. Both of these topological theorems have stronger versions (Borsuk-Ulam and Lusternik-Schnirelmann theorems on anti-inflammatory points). In the paper, the authors show a combinatorial analogue of Borsuk-Ulam theorem and use it to directly prove the Sperner lemma, closing the stronger trinity of theorems.

Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam Equivalent that Directly Implies Sperner's Lemma. The American Mathematical Monthly 120 (2017), no. 4, 346-354.

During the seminar I will present three statements about finite sets with evidence. Two of them are classic theorems of combinatorial power theory - theorems of Sperner and Erdős-Ko-Rado. The third of these is one of the most important theorems in finite set theory - the Hall theorem.

Martin Aigner, Günter M. Ziegler. Chapter 27 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

In computer game 'Lemmings', lemmings are placed in a level walking towards certain direction. When they encounter a wall, they turn and walk back in the direction they came from and when they encounter a hole, they fall. If a lemming falls beyond a certain distance, it dies. The goal is to guide lemmings to the exit by assigning them skills and modifying their behavior. I will show by polynomial-time reduction from 3-SAT that deciding whether particular level is solvable is an NP-Complete problem. This holds even if there is only one lemming in the level to save.

Graham Cormode. The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

Parameterized algorithms can solve some optimization problems quickly, assuming a certain parameter is bounded: for example, when we aim to satisfy a SAT formula by setting at most k (out of n) variables to true. However, the same algorithms directly applied to the unbounded case (k = n) usually yield poor results. Here I will discuss a bridge between parameterized algorithms and general exact exponential-time algorithms. I will show a remarkably simple approach to obtaining a good exact exponential-time algorithm, given a good parameterized algorithm. The resulting algorithm will be randomized, but it is also possible to derandomize it with subexponential additional cost in the complexity. This approach, at the time of publishing, pushed the state-of-the-art for many optimization problems.

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh. Exact Algorithms via Monotone Local Search. arXiv. 2015.

Simple and effective algorithms solving the problem of finding maximum matchings in bipartite graphs had been known for years before a low-complexity algorithm for non-bipartite graphs was published for the first time. That algorithm is known as the Micali-Vazirani algorithm, and it constitutes an intricate combination of the Hopcroft-Karp algorithm for bipartite graphs and the Blossom algorithm for general graphs. It achieves the complexity of O(m√n), which demonstrates that matchings in general graphs are not harder to find than matchings in bipartite ones. We present an intuitive introduction to the algorithm, explaining its main definitions and procedures.

Vijay V. Vazirani. A Simplification of the MV Matching Algorithm and its Proof. arXiv. 2012.

During the seminar will be presented proofs of the seemingly geometrical problem of tiling a rectangle with tiles with at least one side of total length.

Martin Aigner, Günter M. Ziegler. Chapter 26 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

Computer games are a well-studied branch of the theory of complexity. Many of them fit into a similar scheme, lying in the NP (and even NP-hard) and, thanks to Savitch's Theorem, in PSPACE (-hard). It turns out, however, that some of them, thanks to their unique mechanics, are able to simulate the operation of the Turing Machine and thus pose undecidable problems! An interesting example of such a game is Braid, on which this presentation is based. We will start by showing differences and similarities with other games, then we will show how to simulate the operation of the abstract 'counter machine' and talk about a particularly interesting variant of the game, which introduces an TM model that, when it writes to the tape, deletes all data on the tape to the right of the head. And despite the fact that it looks like simplified variant, it lies in EXPSPACE, making Braid a totally 'non-schematic' game.

In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a brilliant and totally unexpected solution, using the “Borsuk–Ulam theorem” from topology, was found by László Lovász twenty-three years later. It happens often in mathematics that once a proof for a long-standing problem is found, a shorter one quickly follows, and so it was in this case. Within weeks Imre Bárány showed how to combine the Borsuk–Ulam theorem with another known result to elegantly settle Kneser’s conjecture. Then in 2002 Joshua Greene, an undergraduate student, simplified Bárány’s argument even further, and it is his version of the proof that I present here.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

We’ll cover the Turan theorem from 1941, which provides a restriction on the number of edges in a graph that doesn’t contain an induced k-clique, depending on parameter k.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

General schemes relating the computational complex-ity of a video game to the presence of certain common elements or mechan-ics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Proofs of complexity of several video games, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft.

Giovanni Viglietta. Gaming is a hard job, but someone has to do it! arXiv. 2013.

In 1978 Thomason provided a simple, constructive proof of Smith’s theorem; in particular this proof provides a simple algorithm enables one to find a second Hamiltonian cycle whenever one is given a cubic graph and a Hamiltonian cycle in it. For a couple of years, the runtime of the algorithm remained unknown, with worst known cases being cubic (in the number of vertices), however in 1999 Krawczyk found an example of a graph family, such that Thomason’s algorithm takes time Ω(2^n/8) where is the number of vertices in the input graph from the family.

In this talk, I will present a family of cubic, planar, and 3-connected graphs, such that Thomason’s algorithm takes time Θ(1.1812ⁿ) on the graphs in this family. This scaling is currently the best known.

Let's consider the following game: we have two players (they are called the angel and the devil) and an infinite chessboard. The angel is located in some cell on the board. Players make moves alternatively. The devil chooses any cell that is not occupied by the angle and blocks it. The angel can jump to any other cell which is at distance at most p (p is fixed) from its present location and is not blocked. The devil wins if the angel cannot jump to any other cell. The angel wins if it can avoid being captured forever. We will show that the angel of power 2 has a winning strategy.

András Máthé. The Angel of power 2 wins. Combinatorics, Probability and Computing 16 (2007), no. 3, 363–374.

The presentation will cover the topic of distributed tracing, which is an important issue in the field of distributed systems. Services are nowadays implemented as complex networks of related sub-systems and it is often hard to determine the source of performance problem in such complex structures. We will take a look at Dapper, a large-scale distributed systems tracing infrastructure, and discuss the challenges its designers had to face, as well as the opportunities the tool gives to programmers. We will discuss the core goals of effective instrumentation, analyze the problem of handling huge amount of tracing data and focus on security concerns.

Online maximum matching problem has a recourse of k, when the decision whether to accept an edge to a matching can be changed k times, where k is typically a small constant. First, we consider the model in which arriving edge never disapears. We show that greedy algorithm has competitive ratio of 3/2 for even k and 2 for odd k. Then we show an improvement for typical values of k and proceed to show a lower bound of 1+1/(k-1). Later, we discuss a model where edges can appear and disappear at any time and show generalized algorithms.

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. arXiv. 2018.

At the seminar were presented some interesting open problems in the field of graph theory.

In 1740 Leonhard Euler began to work on counting partitions. It resulted in two fundamental papers in the field. Integer partitions have been an active field of study ever since, tackled by many including Srinivasa Ramanujan, Paul Erdős and Donald Knuth. We present a few beautiful proofs of identities using only basic generating functions and simple bijections.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

We will introduce a class of graphs called 3CCP, which contains graphs that are 3-connected, cubic (3-regular) and planar. It was shown by Tarjan that finding Hamiltonian cycle in a graph assuming these properties remains NP-complete - we will show the reduction from 3-SAT problem. After that we will present Smith's theorem about parity of number of Hamiltonian cycles containing given edge in cubic graphs and show elegant constructive proof using Thomason's lollipop method. After that we will show a class of graphs for which previous algorithm for finding second Hamiltonian cycle takes exponential number of steps.

For each cell (i, j) of NxN square there is given a list C(i, j) of N colors. Can we choose a color for each cell in such a way that colors in each row and each column are distinct?

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

What do the birthday paradox, the coupon collector problem and shuffling cards have in common? What does it mean for a deck of cards to be "random" or "close to random"? How long does one have to shuffle a deck of cards until it is random? In practical use cases, the question is not about the asymptote - it is about the exact numbers.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

Main aim of the lecture is the answer for Claude Shannon's question from 1956: "Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?"

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

First, several proofs for the number of labeled trees, each using different approach (bijection, linear algebra, recursion, double counting) will be presented. Second part of the seminar will introduce an interesting graph problem first raised by Victor Klee in 1973. This problem can be represented as placing guards in a museum to guard it properly - that is area of the museum must be completely covered by the field of view of the guards.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

Four color theorem was proven in 1976 with extensive computer help. Since then there is interest in finding a simpler proof that uses no computer computation. I will present relation between Four Color Theorem and edge 3-coloring of planar, cubic graphs without bridges, and a new result proving that the existence of approximate coloring (with the fourth color used ‘rarely’) is enough to imply Four Color Theorem.

Atish Das Sarma, Amita S. Gajewar, Richard Lipton, Danupon Nanongkai. An approximate restatement of the four-color theorem. Journal of Graph Algorithms and Applications 17(5), pages 567–573, 2013.

A palindrome is a string which reads the same forward as backward, such as `Ada` or `lol`. We will present a data structure which stores information about all the different palindromic substrings of a given string and prove some basic facts about the data structure. We will show that it is useful and discuss some problems which can be solved with it.

Mikhail Rubinchik, Arseny M. Shur. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. arXiv, pages 1-21, 2015.

Consensus is one of the most important goals to be achieved when many distributed computers share the same task and resources. There are two main families of algorithms solving this problem. Traditional consensus protocols require O(n²) communication, while blockchains rely on proof-of-work. In this talk we will introduce a new family of leaderless Byzantine fault tolerance protocols, built on a metastable mechanism. These protocols provide a strong probabilistic safety and are both quiescent and green. We will analyze some of their properties and guarantees. Finally we will see results of porting Bitcoin transactions to the introduced family of protocols.

Team Rocket. Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies. 2018.

Colorability and choosability of planar graphs have been heavily studied in the past. In 1994 Thomassen proved that every planar graph is 5-choosable using concise induction. Recently Grytczuk and Zhu used similar ideas to prove that for every planar graph G we can find a matching M in it such that G-M is 4-choosable with the help of Combinatorial Nullstellensatz theorem.

Between the well-known concepts of k-colorability and k-choosability (also know as k-list colorability) lies a whole spectrum of more refined notions. This allows for seeing k-colorability and k-choosability under one unified framework. Exploring this, one immediately discovers interesting problems - for example, possible strengthenings of the four color theorem. We will take a look at these notions, prove some of their properties, and leave many conjectures and open problems.

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, Piotr Sankowski: Contracting a Planar Graph Efficiently. CoRR abs/1706.10228 (2017)

Jakub Łabaj. Contracting a Planar Graph Efficiently. slides. 2018.

In this talk I will present upper bound for a queue-number of graphs with bounded tree-width obtained by Veit Wiechert. The new upper bound, 2k - 1, improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. Additionally I will show his construction of k-trees that have queue-number at least k + 1. The construction solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queue-number of 2-trees is equal to 3.

Veit Wiechert. On the queue-number of graphs with bounded tree-width. Electronic Journal of Combinatorics, 24(1):1-14, 2017.

Marcin Muszalski. Queue-number of graphs with bounded tree-width - Veit Wiechert. slides. 2018.

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={v₁,v₂,...,v_k} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector D_u(B)=(d₁,₂,...,d_k) whose components d_i=d_G(u,v_i), 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.

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.

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound. This is a joint work with Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz. A Tight Bound for Shortest Augmenting Paths on Trees. arXiv, pages 1-22, 2017.

The Hadwiger-Nelson problem asks for the minimum number of colors required to color the plane, in such a way, that any two points at distance exactly one are assigned different colors. Albeit its simple definition, no significant progress on the question was made for nearly a century. In the discussed paper, Aubrey D. N. J. de Grey has shown a set of points in the plane, such that 5 colors are necessary to color it properly, thus improving a long-standing lower bound of 4 colors. Interestingly, the smallest such set discovered so far has 1581 vertices.

An F-free coloring is a coloring of a graph such that each color induces an F-free graph. In this talk we consider dynamic F-free coloring which can be interpreted as a game of Presenter and Painter. In each move Presenter presents new vertices along with the edges between them and already known vertices. In the same move Presenter can also discolor arbitrary vertices and request Painter to color some vertices. The problem we consider can be stated as follows: For a given graph G, is there a sequence of moves for which the greedy algorithm uses at least k colors during dynamic F-free coloring of G. We will show that for some classes of graphs this problem is decidable in polynomial time (for fixed F and k) in the case where F is 2-connected or F is path of length 2.

In this talk we will consider the ANTS (Ants Nearby Treasure Search) problem: consider n agents (ants), controlled by finite automata (or PDAs) exploring an infinite grid attempting to locate a hidden treasure. The question we want to answer is: how many agents are necessary to accomplish this task in (expected) finite time? Of course, the answer will depend on the way we model this situation. We will consider synchronous as well as asynchronous environment, agents with access to randomness as well as deterministic ones, agents controlled by PDA as well as finite automata and various combinations thereof. In most cases established bounds are tight, however in certain cases there is still ample room for improvement (which some might consider interesting).

I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant):
Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S.
They created first superlinear lower bound for the number of maximum-volume empty boxes amidst n points in R d (d ≥ 3). I would like to present it and show a prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log(n) 2^α(n) ), where α(n) is the extremely slowly growing inverse of Ackermann’s function. The previous best bound for this problem, O(n^2 ), is due to Naamad, Lee, and Hsu (1984).

In 2008 Klaus Jansen and Roberto Solis-Oba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented.

S. Heydrich, A. Wiese, Faster approximation schemes for the two-dimensional knapsack problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 79-98

In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs.

Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles.

Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109

Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if:

• G is connected and not bipartite,
• |V_1| = |V_2|
• V_1 \cap V_2 = \emptyset
• Every vertex has degree d
• Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1,
• Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia

A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2.

David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253

Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached.

Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017

This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problem-solving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions.

Simeon Ball, Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica, September 2009, Volume 29, Issue 5, pp 511–522

Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an α-balanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2-balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams.

Emily J. Olson, Bruce E. Sagan, On the 1/3--2/3 Conjecture, Order, 2018

I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems.

Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. arXiv:1310.6482 (2014), pp 1-44.

I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem.

Jarek Duda. Some unusualapproaches to hard computational problems. slides.

Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal water-filling algorithm with competitive ratio 1/(1-1/e) . The main contribution of this paper is a 1.901-competitive algorithm for vertex cover in general graphs which beats the well-known trivial 2-competitive algorithm. The next major result is a primal-dual analysis of given algorithm that implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.

Yajun Wang, Sam Chiu-wai Wong. Online Vertex Cover and Matching: Beating the Greedy Algorithm. arXiv (2013), pp 1-21.

A Feedback Vertex Set (FVS) is a subset of vertices in a graph such that its removal results in an acyclic graph. The problem of finding a minimal FVS is one of the classic NP-complete problems. However, in some practical cases, we can assume that its size is fairly small. This motivated an intensive study of the parametrized version of this problem, which asks either for FVS of a size at most k or an information that it doesn't exist. There are several deterministic algorithms known which solve this in time O^*(c^k), the best one for now being O^*(3.592^k).

On bipartite graphs, problem of constrained minimum vertex cover (MIN-CVCB) is defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U ∪ L and two integers k_u and k_l, decide whether there is a minimum vertex cover in G with at most k_u vertices in U and at most k_l vertices in L. We show how it is related to practical problems. We prove that (MIN-CVCB) is NP-complete. However, there are many parametrized algorithms running in decent time. We describe one of them, whereby linear kernelization method it achieves O(1.26^k_u+k_l +(k_u +k_l)|G|) time.

Jianer Chen, Iyad A.Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences. Vol. 67, Iss. 4, (2003), pp. 833-847.

In a graph G, let B be the set of vertices covered by every maximum matching in G, and let D = V(G) − B. Further partition B by letting A be the subset consisting of vertices with at least one neighbor outside B, and let C = B − A. The Gallai-Edmonds Decomposition of G is the partition of V(G) into the three sets A, C, D. The Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is an extension of the Gallai-Edmonds decomposition.

L. Lovász, M. D. Plummer. Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam. 1986. pp. xxvii+544. ISBN: 0-444-87916-1. Chapter 4.3.

This paper studies the maximum matching in a graph. It shows a short proof of a Berge-Tutte formula and the Gallai-Endmonds structure theorem. Authors use Hall's theorem to prove it. Deficiency in a graph (def(S), S⊆V(G)) is o(G-S) - |S|, where o(G-S) is the number of odd components in G-S. Berge-Tutte formula says that the maximum size of a matching in an n-vertex graph G is 1/2(n-def(G)), where def(G) = max_S⊆V(G)def(S). Gallai Edmonds has a sharper formulation which gives considerable information about the structure of maximum size matchings.

Douglas B.West. A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem. European Journal of Combinatorics. Vol. 32, Iss. 5, (2011), pp. 674-676.

We say that a class C of graphs admits low rank-width colorings if there exist functions N : N → N and Q: N → N such that for all p ∈ N, every graph G ∈ C can be vertex colored with at most N(p) colors such that the union of any i ≤ p color classes induces a subgraph of rank-width at most Q(i). It turns out that for every graph class C of bounded expansion and every positive integer r, the class {G^r : G ∈ C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. Additionally, every graph class admitting low rank-width colorings is χ-bounded.

O-joung Kwon, Michał Pilipczuk, and Sebastian Siebertz. On Low Rank-Width Colorings. arXiv (2017), pp. 1-17.

We introduce two classes of graphs - graphs with bounded expansion and nowhere dense graphs. These notions are a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, to name just a few classes which are studied extensively in combinatorial and computer science contexts. We also present generalized colouring numbers adm_r(G), col_r(G), and wcol_r(G) and show important applications in the theory of above-mentioned classes of graphs. Finally, we prove that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of r, and show that it can be efficiently computed.

Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Vol. 58 (2016), pp. 85:1-85:13.

A vertex coloring of graph G satisfies the majority rule, if for each vertex v at most half of its neighbors receive the same color as v. A coloring which satisfies the majority rule is called majority coloring. We consider its game version. For given graph G and color set C two players, Alice and Bob, in alternating turns color vertices with respect to the majority rule. Alice wins when every vertex becomes colored, while goal for Bob is to create a vertex which cannot be colored with any color belonging to the set C without breaking the majority rule. Let µ_g(G) denote the least number of colors belonging to C for which Alice has winning strategy in game on graph G. We show that if the color set C is finite, there exists a graph G on which Bob has winning strategy. We prove also that for graphs with col(G) = 3 parameter µ_g(G) is still unbounded.

Erdős discrepancy problem has waited for the solution for over 70 years until last year Terrence Tao, with a help of Polymath project, has published a paper with its solution. After having our friends given an introduction to the topic and shown the Fourier analytic reduction of the problem last week we will continue presenting the proof. It will include the proof of Elliot-type conjecture and a sketch of how to apply a generalised Borwein-Choi-Coons analysis for the final steps of the main proof.

Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2 (2016), pp. 1-20.

Erdős discrepancy problem had remained unresolved for more than 80 years. In 2015 Erdős theorem has been proofed by Terrence Tao. We present first part of his proof where he uses a Fourier-analytic reduction obtained as part of the Polymath5 project which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g.

Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2, (2016), pp. 1-20.

We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation.

Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg. Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 101-107, SIAM, Philadelphia, PA, 2012.

We examine the classic on-line bipartite matching problem studied by Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. Algorithm attempts to match online new vertices with edges. Such a decision, once made, is irrevocable. The objective is to maximize the size of the resulting matching. We will see a sketch of simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 − 1/e.

B.E. Birnbaum, C. Mathieu. On-line bipartite matching made simple. SIGACT News 39 (1), 80-87, 2008.

We give insight into competitive reachability for outerplanar graphs and also for other classes of graphs with bounded degree. Competitive reachability is a game where two players orient the edges of undirected graph G alternately until all edges of G have been oriented. One player wants to minimize the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. And the second want to maximize it.

Furthermore we focus on harmonious coloring conjecture for outerplanar graphs and further attempts in this area. A harmonious coloring of a graph G is a proper vertex coloring of G in which every pair of colors appears on adjacent vertices at most once. The harmonious chromatic number, denoted by h(G), is the minimum number of colors in a harmonious coloring. Analogically we define  harmonious edge coloring in which every pair of colors appears on incident edges at most once. The minimal number of color we denote by h'(G). The conjecture states that h(G)<=h'(G).

Finally we tackle the hamiltonian cycles in grid graphs. Grid graph are finite vertex induced subsets of infinite lattice, composed from unit-side squares, equilateral triangles or equilateral hexagons. Decide whether the grid graph has hamiltonian cycle is NP-hard in general.

• Noah Kravitz, Stefan Steinerberger Ulam Sequences and Ulam Sets

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

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.

• A Note on Boolean Dimension of Posets, J. Nešetřil, P. Pudlák, Irregularities of Partitions, 137-140, 1989

1. Hadwiger's Conjecture
2. Seagull Conjecture
3. Jorgensen's Conjecture
4. Unfriendly partitions
5. and a few more conjectures concerning minors.

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

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

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.

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

The talk presents a joint work of Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak. 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={v₁,v₂,…,v_k} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector D_u(B)=(d₁,d₂,…,d_k) whose components d_i=d_G(u,v_i), 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 localize 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.

I present an O(n^2*log n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2*log n) time if the difference between the maximum degree and the minimum degree is less than r.

R. Yuster, Maximum matching in regular and almost regular 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

Extending the results presented on the preceding seminar, we study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2, and for trees, we consider any k>=2. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.

L. M. Favrholdt, J. W. Mikkelsen, Online Dual Edge Coloring of Paths and Trees

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and 1/2 , and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than 4/7 -competitive. If the graphs are all k-colorable, any fair algorithm is at least 1/2 -competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.

M. Favrholdt, N. Nielsen, On-Line Edge-Coloring with a Fixed Number of Colors, Algorithimca 35 (2), 176-191, 2003

We consider the number of linear extensions of an N-free order P. We give upper and lower bounds on this number in terms of parameters of the corresponding arc diagram. We propose a dynamic programming algorithm to calculate the number. The algorithm is polynomial if a new parameter called activity is bounded by a constant. The activity can be bounded in terms of parameters of the arc diagram.

Stefan Felsner , Thibault Manneville, Linear Extensions of N-free Orders, Order 32 (2), 147-155, 2015

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight.  The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms.

L. Epstein, A. Levin, D. Segev, O. Weimann, Online Preemptive Matching, arXiv 2012

A connected graph has tree-depth at most k if it is a subgraph of the clusure of a rooted tree whose height is at most k. The autors give an algorithm which for a given n-vertex graph G, in time O(1.9602^n) computes the tree-depth of G. The algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain G.

F. V. Fomin, A. C. Giannopoulou, M. Pilipczuk, Computing Tree-Depth Faster Than 2^n, Algorithmica 73 (1), 202-216, 2015

In this article autors introduce a new notion of α-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least α positions in w. They develop a data structure of O(n) size (where n=|w|) that can be constructed in O(nlogn) time which they apply to compute all shortest α-partial covers for a given α. They also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n.

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski , Wojciech Rytter, Tomasz Waleń, Fast Algorithm for Partial Covers in Words, Algorithmica 73 (1), 217-233, 2015

In my presentation I will discus some elementary dynamic problems (Single source reachability and Dynamic diameter) and then I will present interesting reduction from this problems to Orthogonal Vectors Problems. These reductions imply that if it would be possible to solve SSR in O(m^(1-ε)) or do 1.3 approximation of DD in O(m^(2-ε)) then SETH will be refuted.

Amir Abboud, Popular Conjectures and Dynamic Problems, 2015

Some graph problems (such as such as APSP, negative triangle, distance product or radius) do not have any known solutions better then the naive ones. We show subquadraic and subcubic reductions between them, proving that in case of finding a faster algorithm for any of the problems would be equivalent of reducing the complexity of each of them. We separate algorithms for sparse and dense graphs and focus on basic methods for both classes.

V. Williams, Conditional hardness and equivalences for graph problems

Introduction into a young branch of algorithmics. We discuss why we are stuck during developing fast algorithms to some well-known problems. Problems in P and suitable reductions form equivalence classes of problems, inside which improving asymptotic time of any of them would automatically improve the rest. At the bottom of these classes lie problems such as: 3SUM, all-pairs-shortest-paths, orthogonal vectors. Their complexities are guarded by strong conjectures which, if proven wrong, would revoke widely believed conjectures such as SETH.  

Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams, Hardness for easy problems - An introduction, 2015