Lukáš Folwarczný
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Lukáš Folwarczný has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Jiří Sgall
Computer Science Institute Faculty of Mathematics and Physics of Charles University Prague Czech Republic
3 shared publications - Dušan Knop
Czech Technical University in Prague
2 shared publications - Marcin Bienkowski
University of Wroclaw, Wroclaw, Poland
2 shared publications - Martin Böhm
University of Wrocław
2 shared publications Christoph Dürr
1 shared publication- Christoph Dürr
Sorbonne University
1 shared publication
Latest Publications
- 23 September 2023
- Published by Springer Nature
- p. 305-318
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
- 23 September 2023
- Published by Springer Nature
- p. 305-318
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
- Open Access
- 31 March 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 15 (1-2) , 1-17
On Protocols for Monotone Feasible Interpolation
Dag-like communication protocols, a generalization of the classical tree-like communication protocols, are useful objects in the realm of proof complexity (most importantly for monotone feasible interpolation) and circuit complexity. We consider three kinds of protocols in this article ( d is the degree of a protocol): — IEQ- d -dags: feasible sets of these protocols are described by inequality which means that the feasible sets are combinatorial triangles; these protocols are also called triangle-dags in the literature, — EQ- d -dags: feasible sets are described by equality, and — c -IEQ- d -dags: feasible sets are described by a conjunction of c inequalities. Garg, Göös, Kamath, and Sokolov (Theory of Computing, 2020) mentioned all these protocols, and they noted that EQ- d -dags are a special case of c -IEQ- d -dags. The exact relationship between these types of protocols is unclear. As our main contribution, we prove the following statement: EQ-2-dags can efficiently simulate c -IEQ- d -dags when c and d are constants. This implies that EQ-2-dags are at least as strong as IEQ- d -dags and that EQ-2-dags have the same strength as c -IEQ- d -dags for c ≥ 2 (because 2-IEQ-2-dags can trivially simulate EQ-2-dags). Hrubeš and Pudlák (Information Processing Letters, 2018) proved that IEQ- d -dags over the monotone Karchmer-Wigderson relation are equivalent to monotone real circuits which implies that we have exponential lower bounds for these protocols. Lower bounds for EQ-2-dags would directly imply lower bounds for the proof system R(LIN).
- 31 March 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 15 (1-2) , 1-17
Open AccessOn Protocols for Monotone Feasible Interpolation
Dag-like communication protocols, a generalization of the classical tree-like communication protocols, are useful objects in the realm of proof complexity (most importantly for monotone feasible interpolation) and circuit complexity. We consider three kinds of protocols in this article ( d is the degree of a protocol): — IEQ- d -dags: feasible sets of these protocols are described by inequality which means that the feasible sets are combinatorial triangles; these protocols are also called triangle-dags in the literature, — EQ- d -dags: feasible sets are described by equality, and — c -IEQ- d -dags: feasible sets are described by a conjunction of c inequalities. Garg, Göös, Kamath, and Sokolov (Theory of Computing, 2020) mentioned all these protocols, and they noted that EQ- d -dags are a special case of c -IEQ- d -dags. The exact relationship between these types of protocols is unclear. As our main contribution, we prove the following statement: EQ-2-dags can efficiently simulate c -IEQ- d -dags when c and d are constants. This implies that EQ-2-dags are at least as strong as IEQ- d -dags and that EQ-2-dags have the same strength as c -IEQ- d -dags for c ≥ 2 (because 2-IEQ-2-dags can trivially simulate EQ-2-dags). Hrubeš and Pudlák (Information Processing Letters, 2018) proved that IEQ- d -dags over the monotone Karchmer-Wigderson relation are equivalent to monotone real circuits which implies that we have exponential lower bounds for these protocols. Lower bounds for EQ-2-dags would directly imply lower bounds for the proof system R(LIN).
- 1 March 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 861, 133-143
New results on multi-level aggregation
- 1 March 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 861, 133-143
New results on multi-level aggregation
- 1 January 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (1) , 214-232
Online Algorithms for Multilevel Aggregation
Online Algorithms for Hierarchical Aggregation Problems Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
- 1 January 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (1) , 214-232
Online Algorithms for Multilevel Aggregation
Online Algorithms for Hierarchical Aggregation Problems Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
- 1 September 2017
- Published by Elsevier in Information Processing Letters
- Vol. 125, 5-8
-matching is strongly NP-hard- 1 September 2017
- Published by Elsevier in Information Processing Letters
- Vol. 125, 5-8
-matching is strongly NP-hard- 19 August 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (2) , 319-339
General Caching Is Hard: Even with Small Pages
- 19 August 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (2) , 319-339
General Caching Is Hard: Even with Small Pages
- 27 November 2015
- Published by Springer Nature
- p. 116-126
General Caching Is Hard: Even with Small Pages
- 27 November 2015
- Published by Springer Nature
- p. 116-126
General Caching Is Hard: Even with Small Pages
- Open Access
IV-matching is strongly NP-hard
IV-matching is a generalization of perfect bipartite matching. The complexity of finding IV-matching in a graph was posted as an open problem at the ICALP 2014 conference. In this note, we resolve the question and prove that, contrary to the expectations of the authors, the given problem is strongly NP-hard (already in the simplest non-trivial case of four layers). Hence it is unlikely that there would be an efficient (polynomial or pseudo-polynomial) algorithm solving the problem.
Open AccessIV-matching is strongly NP-hard
IV-matching is a generalization of perfect bipartite matching. The complexity of finding IV-matching in a graph was posted as an open problem at the ICALP 2014 conference. In this note, we resolve the question and prove that, contrary to the expectations of the authors, the given problem is strongly NP-hard (already in the simplest non-trivial case of four layers). Hence it is unlikely that there would be an efficient (polynomial or pseudo-polynomial) algorithm solving the problem.