Instytut Informatyki Analitycznej - lista publikacji

On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width, IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE [LICS] vol. 35TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2020) (2020), 958-971

319.

Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width, INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE [STACS] vol. 154 (LIPIcs) (2020), 39:1-39:16

318.

Lech Duraj

A Sub-Quadratic Algorithm for the Longest Common Increasing Subsequence Problem, INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE [STACS] vol. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (2020), 41:1-41:18

317.

Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter

Local dimension is unbounded for planar posets, ELECTRON J COMB vol. 27(4) (2020), P4.28

316.

Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin

Adjacency labelling for planar graphs (and beyond), (2020), "2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)", Institute of Electrical and Electronics Engineers (IEEE)

315.

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood

Planar Graphs Have Bounded Queue-Number, J ACM (2020),

314.

Stefan Felsner, Tamás Mészáros, Piotr Micek

Boolean Dimension and Tree-Width, COMBINATORICA vol. 40 (2020), 655-677

313.

Michał Dębski, Stefan Felsner, Piotr Micek, Felix Schröder

Improved bounds for centered colorings vol. SODA '20 (2020), "Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms", Society for Industrial and Applied Mathematics (SIAM)

312.

Tamás Mészáros, Piotr Micek, William T. Trotter

Boolean Dimension, Components and Blocks, ORDER (2020), 287-298

311.

Libor Barto, Tan Johnson, Marcin Kozik, Matthew Valeriote

Sensitive Instances of the Constraint Satisfaction Problem, INTERNATIONAL COLLOQUIUM ON AUTOMATA LANGUAGES AND PROGRAMMING [ICALP](MAIN), (2020), 110:1--110:18

310.

Abram Magner, Wojciech Szpankowski, Krzysztof Turowski

Compression of Dynamic Graphs Generated by a Duplication Model, ALGORITHMICA vol. 82 (2020), 2687-2707

309.

Piotr Kawałek, Jacek Krzaczkowski

Even faster algorithms for CSAT over supernilpotent algebras, INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE [MFCS] vol. 170 (2020), 55:1--55:13

308.

Grzegorz Herman

Faster general parsing through context-free memoization, ACM-SIGPLAN CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION [PLDI], (2020), 1022-1035

307.

Csaba Biró, Bartłomiej Bosek, Heather C. Smith, William T. Trotter, Ruidong Wang, Stephen J. Young

Planar Posets that are Accessible from Below Have Dimension at Most 6, ORDER (2020),

306.

Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, Anna Zych-Pawlewicz

Recoloring Interval Graphs with Limited Recourse Budget vol. 162 (2020), "17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

305.

Zofia Kostrzycka, Marek Zaionc

Quantitative Study of Fuzzy Logics, 2020 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ-IEEE) (2020), 1-8

304.

Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski

Intermediate problems in modular circuits satisfiability, (2020), "LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science", Association for Computing Machinery (ACM)

303.

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak, Joanna Sokół

Online Coloring of Short Intervals, INTERNATIONAL WORKSHOP ON APPROXIMATION ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS (APPROX) vol. 176 (2020), 52:1–52:18

302.

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon

Online metric algorithms with untrusted predictions, INTERNATIONAL CONFERENCE ON MACHINE LEARNING (ICML) vol. 119 (2020), 345–355

301.

Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood

Planar graphs have bounded nonrepetitive chromatic number, ADVANCES IN COMBINATORICS vol. 2020 (2020), 5:1-11

300.

Marcin Kozik

Solving CSPs using weak local consistency, SIAM J COMPUT (2020), to appear

299.

Michał Seweryn

Improved bound for the dimension of posets of treewidth two, DISCRETE MATH (2020), 111605

298.

Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions, 11TH INNOVATIONS IN THEORETICAL COMPUTER SCIENCE CONFERENCE (ITCS 2020) vol. 151 (Leibniz International Proceedings in Informatics (LIPIcs)) (2020), 53:1-53:18

297.

Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams

Equivalences between triangle and range query problems, ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS 2020 (SODA'20) (2020), 30-47

2019

296.

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood

Planar Graphs have Bounded Queue-Number, (2019), "2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)", Institute of Electrical and Electronics Engineers (IEEE)

295.

Gal Kronenberg, Christopher Kusch, Ander Lamaison, Piotr Micek, Tuan Tran

A note on the minimum number of edges in hypergraphs with property O, EUR J COMBIN vol. 81 (2019), 172-177

294.

Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Piotr Micek, Heather C. Smith, Libby Taylor, William T. Trotter

Separating tree-chromatic number from path-chromatic number, J COMB THEORY B vol. 138 (2019), 206-218

293.

Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez, Veit Wiechert

Nowhere dense graph classes and dimension, COMBINATORICA (2019), 1055-1079

292.

Robert Janczewski, Paweł Obszarski, Krzysztof Turowski

2-Coloring number revisited, THEOR COMPUT SCI vol. 796 (2019), 187-195

291.

Neininger Ralph, Hwang, Hsien-Kuei

Preface, COMB PROBAB COMPUT vol. 28(4) (2019), 483-484

290.

Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, SIAM J COMPUT vol. 48(6) (2019), 1763–1795

289.

Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak

Subexponential-time algorithms for finding large induced sparse subgraphs vol. 148 of Leibniz International Proceedings in Informatics (2019), "14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

288.

Alexandre Rok, Bartosz Walczak

Outerstring graphs are χ-bounded, SIAM J DISCRETE MATH vol. 33 (2019), 2181-2199

287.

Coloring triangle-free L-graphs with O(log log n) colors, AMUC vol. 88 (2019), 1063-1069

286.

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk

Majority coloring of infinite digraphs, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE vol. 88 (3) (2019), 371-376

285.

Maciej Bendkowski, Pierre Lescanne

On the enumeration of closures and environments with an application to random generation, LOG METH COMPUT SCI vol. 15, Issue 4 (2019), 3:1–3:21

284.

Maciej Bendkowski, Olivier Bodini, Sergey Dovgal

Statistical Properties of Lambda Terms, ELECTRON J COMB vol. 26, Issue 4 (2019), 70

283.

Grzegorz Guśpiel

Smaller Universal Targets for Homomorphisms of Edge-Colored Graphs, COMPUTING AND COMBINATORICS, 25TH INTERNATIONAL CONFERENCE, COCOON 2019, XI'AN, CHINA, JULY 29–31, 2019, PROCEEDINGS vol. 11653 (2019), 232-239

282.

Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi

Connecting the Dots (with Minimum Crossings), 35TH INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY vol. 129 (2019), 7:1-7:17

281.

Maciej Bendkowski

Towards the average-case analysis of substitution resolution in λ-calculus vol. Leibniz International Proceedings in Informatics (LIPIcs) (2019), "4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

280.

Lech Duraj, Marvin Künnemann, Adam Polak

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence, ALGORITHMICA (2019), 25 pages

279.

Alexandre Rok, Bartosz Walczak

Coloring curves that cross a fixed curve, DISCRETE COMPUT GEOM vol. 61 (2019), 830-851

278.

The Complexity of Minimal Inference Problem for Conservative Constraint Languages, ACM T COMPUT LOG vol. 20(2) (2019),

277.

Bartłomiej Bosek, Michał Farnik, Jarosław Grytczuk, Sebastian Czerwiński, Tomasz Bartnicki, Zofia Miechowicz

Generalized arboricity of graphs with large girth, DISCRETE MATH vol. 342(5) (2019), 1343-1350

276.

David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang

Dimension of posets with planar cover graphs excluding two long incomparable chains, J COMB THEORY A vol. 164 (2019), 1-23

275.

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk

Weight choosability of oriented hypergraphs, ARS MATH CONTEMP vol. 16 (1) (2019), 111-117

274.

Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak

Majority coloring game, DISCRETE APPL MATH vol. 255 (2019), 15-20

2018

273.

Kolja Knauer, Piotr Micek, Torsten Ueckerdt

The Queue-Number of Posets of Bounded Width or Height vol. 11282 of Lecture Notes in Computer Science (2018), "Graph Drawing and Network Visualization. GD 2018", Springer

272.

Gwenaël Joret, Piotr Micek, Veit Wiechert

Sparsity and dimension, COMBINATORICA vol. 38 (2018), 1129-1148

271.

Abram Magner, Wojciech Szpankowski, Krzysztof Turowski

Lossless Compression of Binary Trees With Correlated Vertex Names, IEEE T INFORM THEORY vol. 64 (9) (2018), 6070-6080

270.

Tomasz Kisielewski, Damian Leśniak

Accidental exploration through value predictors, SCHEDAE INFORMATICAE vol. 27 (2018),

269.

Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert

Burling Graphs, Chromatic Number, and Orthogonal Tree-Decompositions, ELECTRON J COMB vol. 25 (1) (2018), P1.35

268.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak

Centroidal Localization Game, ELECTRON J COMB vol. 25 (4) (2018), 1-19

267.

Mikkel Abrahamsen, Bartosz Walczak

Common tangents of two disjoint polygons in linear time and constant workspace, ACM T ALGORITHMS vol. 15 (2018), 12:1-21

266.

Łukasz Lachowski

On the Complexity of the Standard Translation of Lambda Calculus into Combinatory Logic, REPORTS ON MATHEMATICAL LOGIC vol. 53 (2018), 19-42

265.

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, DISCRETE APPL MATH vol. 251 (2018), 30-39

264.

Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski

Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras vol. Leibniz International Proceedings in Informatics (LIPIcs) (2018), "43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

263.

Paweł Idziak, Jacek Krzaczkowski

Satisfiability in multi-valued circuits, (2018), "Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'18)", Association for Computing Machinery (ACM)

262.

Maciej Bendkowski, Pierre Lescanne

Combinatorics of explicit substitutions vol. PPDP '18 (2018), "Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming", Association for Computing Machinery (ACM)

261.

Lech Duraj, Grzegorz Gutowski, Jakub Kozik

A note on two-colorability of nonuniform hypergraphs, LIPICS–LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS vol. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (2018), 46:1--46:13

260.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz

A Tight Bound for Shortest Augmenting Paths on Trees vol. 10870 (2018), "LATIN 2018: Theoretical Informatics", Springer

259.

Maciej Bendkowski, Pierre Lescanne

Counting Environments and Closures vol. Leibniz International Proceedings in Informatics (LIPIcs) (2018), "3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

258.

Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak

Sparse Kneser graphs are Hamiltonian, (2018), "Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC’18)", Association for Computing Machinery (ACM)

257.

Aleksander Byrski, Kevin Hammond, John Hughes, Wojciech Turek, Marek Zaionc

Foreword to the Special Issue on Parallel and Distributed Computing based on The Functional Programming Paradigm, CONCURR COMP-PRACT E (2018), 4

256.

Alexandr Kazda, Marcin Kozik, Ralph McKenzie, Matthew Moore

Absorption and directed Jónsson terms, (2018), "Don Pigozzi on Abstract Algebraic Logic", Springer

255.

Grzegorz Gutowski, Ming Han, Tomasz Krawczyk, Xuding Zhu

Defective 3-Paintability of Planar Graphs, ELECTRON J COMB vol. 25 (2) (2018), 20

254.

William T. Trotter, Bartosz Walczak, Ruidong Wang

Dimension and cut vertices: an application of Ramsey theory, (2018), "Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham", Cambridge University Press

253.

Bartłomiej Bosek, H. A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, Matthew Smith

An Easy Subexponential Bound for Online Chain Partitioning, ELECTRON J COMB vol. 25(2) (2018), #P2.28

252.

Jakub Kozik, Grzegorz Matecki

Deferred On-Line Bipartite Matching, ELECTRON J COMB vol. 25 (2) (2018), P2.24

251.

Grzegorz Gutowski

Every Plane Graph is Facially-Non-Repetitively C-choosable, ELECTRON J COMB vol. 25 (1) (2018), 13

250.

Patryk Mikos

A new lower bound for the on-line coloring of intervals with bandwidth, THEOR COMPUT SCI vol. 708 (2018), 96-100

249.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz

Shortest Augmenting Paths for Online Matchings on Trees, THEOR COMPUT SYST vol. 62(2) (2018), 337-348

248.

Bartłomiej Bosek, Michał Dębski, Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak, Wiktor Żelazny

Graph coloring and Graham’s greatest common divisor problem, DISCRETE MATH vol. 341(3) (2018), 781-785

247.

Maciej Bendkowski, Olivier Bodini, Sergey Dovgal

Polynomial tuning of multiparametric combinatorial samplers, (2018), "2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)", Society for Industrial and Applied Mathematics (SIAM)

246.

Karol Kosiński, Robert Mercas, Dirk Nowotka

Corrigendum to "A note on Thue games" [Inf. Process. Lett. 118 (2017) 75-77], INFORM PROCESS LETT vol. 130 (2018), 63-65

245.

Adam Polak

Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequence?, INFORM PROCESS LETT vol. 132 (2018), 1-5

244.

Grzegorz Guśpiel, Piotr Micek, Adam Polak

On an Extremal Problem for Poset Dimension, ORDER vol. 35(3) (2018), 489-493

243.

Maciej Bendkowski, Katarzyna Grygiel, Paul Tarau

Random generation of closed simply-typed λ-terms: a synergy between logic programming and Boltzmann samplers, THEOR PRACT LOG PROG vol. 18(1) (2018), 97-119

242.

Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta

The Partial Visibility Representation Extension Problem, ALGORITHMICA vol. 80 (8) (2018), 2286-2323

2017

241.

William T. Trotter, Bartosz Walczak

Boolean dimension and local dimension vol. 61 of Electronic Notes in Discrete Mathematics (2017), "The Ninth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017", Elsevier Science

240.

Gwenaël Joret, Piotr Micek, William T. Trotter, Ruidong Wang, Veit Wiechert

On the Dimension of Posets with Cover Graphs of Treewidth 2, ORDER vol. 34.2 (2017), 185-234

239.

Piotr Micek, Veit Wiechert

Topological minors of cover graphs and dimension, J GRAPH THEOR vol. 86.3 (2017), 295–314

238.

Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert

Burling graphs, chromatic number, and orthogonal tree-decompositions, ELECTRONIC NOTES IN DISCRETE MATHEMATICS vol. 61 (2017), 415-420

237.

Gwenaël Joret, Piotr Micek, Veit Wiechert

Planar posets have dimension at most linear in their height, SIAM J DISCRETE MATH vol. 31 (4) (2017), 2754–2790

236.

On-line approach to off-line coloring problems on graphs with geometric representations, COMBINATORICA vol. 37 (2017), 1139-1179

235.

Marek Zaionc

Asymptotic density in logic and computability, PROCEEDINGS OF THE TENTH WORKSHOP ON INFORMATION THEORETIC METHODS IN SCIENCE AND ENGINEERING, PARIS, FRANCE, SEPTEMBER 11-13, 2017 vol. Publication series B, Report B-2017-3 (Editors: Jacquet Philippe, Leppä-Aho Janne, Roos Teemu (2017), 43

234.

Extending partial representations of trapezoid graphs vol. 10520 of Lecture Notes in Computer Science (2017), "Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers", Springer

233.

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk

Majority Choosability of Digraphs, ELECTRON J COMB vol. 24(3) (2017), #P3.57

232.

Alexandre Rok, Bartosz Walczak

Coloring curves that cross a fixed curve vol. 77 of Leibniz International Proceedings in Informatics (2017), "33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

231.

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc

Combinatorics of λ-terms: a natural approach, J LOGIC COMPUT vol. Volume 27, Issue 8 (2017), 2611–2630

230.

Grzegorz Guśpiel, Grzegorz Gutowski

Universal targets for homomorphisms of edge-colored graphs, J COMB THEORY B vol. 127 (2017), 53-64

229.

Maciej Brzeski, Przemysław Spurek

Uniform Cross-entropy Clustering, SCHEDAE INFORMATICAE vol. 25 (2017), 117-126

228.

Adam Gągol, Piotr Micek, Bartosz Walczak

Graph sharing game and the structure of weighted graphs with a forbidden subdivision, J GRAPH THEOR vol. 85 (2017), 22-50

227.

The Complexity of Minimal Inference Problem for Conservative Constraint Languages. Proceedings of the Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)., IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE [LICS], (2017),

226.

Minimal Inference Problem over Finite Domains: The Landscape of Complexity. Procedings of the International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR)., INTERNATIONAL CONFERENCE ON LOGIC PROGRAMMING AND NON-MONOTONIC REASONING [LPNMR], (2017),

225.

Barnaby Martin, Andras Pongracz, Michał Wrona

The Complexity of Counting Quantifiers on Equality Languages, THEOR COMPUT SCI vol. 670 (2017), 56–67

224.

Libor Barto, Marcin Kozik

Absorption in Universal Algebra and CSP, (2017), "The Constraint Satisfaction Problem: Complexity and Approximability", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

223.

Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal

Robust algorithms with polynomial loss for near-unanimity CSPs, PROCEEDINGS OF THE 28TH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS SODA'17 (2017), 340-357

222.

Piotr Micek, Veit Wiechert

An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths, ALGORITHMICA vol. 77 (2017), 1060-1070

221.

Grzegorz Gutowski, Patryk Mikos

Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints vol. 10139 (Lecture Notes in Computer Science) (2017), "SOFSEM 2017: Current Trends in Theory and Practice of Computer Science, 43rd International Conference, Limerick, Ireland, January 16-20, 2017, Proceedings", Springer

220.

Maciej Bendkowski, Katarzyna Grygiel, Paul Tarau

Boltzmann Samplers for Closed Simply-Typed Lambda Terms, LECTURE NOTES IN COMPUTER SCIENCE vol. 10137 (2017), 120-135

219.

Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak

On the Beer index of convexity and its variants, DISCRETE COMPUT GEOM vol. 57 (2017), 179-214

218.

Minors and dimension, J COMB THEORY B vol. 122 (2017), 668-689

217.

Maciej Bendkowski, Katarzyna Grygiel, Marek Zaionc

On the likelihood of normalisation in combinatory logic, J LOGIC COMPUT vol. Volume 27, Issue 7 (2017), 2251–2269

2016

216.

Robert Janczewski, Krzysztof Turowski

An O(n log n) algorithm for finding edge span of cacti, J COMB OPTIM vol. 31(4) (2016), 1373-1382

215.

Robert Janczewski, Krzysztof Turowski

On the hardness of computing span of subcubic graphs, INFORM PROCESS LETT vol. 116(1) (2016), 26-32

214.

Tomasz Kisielewski

Criteria for regularity of Mahler power series and Becker's conjecture, J NUMBER THEORY vol. 174 (2016), 456-486

213.

Vida Dujmović, Gwenaël Joret, Jakub Kozik, David R. Wood

Nonrepetitive colouring via entropy compression, COMBINATORICA vol. Volume 36, Issue 6 (2016), 661-686

212.

Piotr Danilewski, Philipp Slusallek

Building Code with Dynamic Staging, THE COMPUTING RESEARCH REPOSITORY (2016), 11

211.

Piotr Danilewski, Philipp Slusallek

ManyDSL: A Host for Many Languages, THE COMPUTING RESEARCH REPOSITORY (2016), 14

210.

Barnaby Martin, Andras Pongracz, Michał Wrona

The Complexity of Counting Quantifiers on Equality Languages, LECTURE NOTES IN COMPUTER SCIENCE vol. 9709 (2016), 333--342

209.

Gwenaël Joret, Piotr Micek, Veit Wiechert

Sparsity and dimension, (2016), "27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), January 10-12, 2016, Arlington, VA, USA", Society for Industrial and Applied Mathematics (SIAM)

208.

Steven Chaplick, Piotr Micek, Torsten Ueckerdt, Veit Wiechert

A note on concurrent graph sharing games, INTEGERS vol. Volume 16, G1 (2016), 5

207.

Adam Gągol, Gwenaël Joret, Jakub Kozik, Piotr Micek

Pathwidth and nonrepetitive list colorings, ELECTRON J COMB vol. Volume 23, Issue 4 (2016), 19

206.

Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta

The Partial Visibility Representation Extension Problem vol. 9801 (Lecture Notes in Computer Science) (2016), "Graph Drawing and Network Visualization, 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers", Springer

205.

Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl

The subpower membership problem for semigroups, INT J ALGEBR COMPUT vol. 26 (2016), 1435-1451

204.

Lech Duraj, Grzegorz Gutowski, Jakub Kozik

Chip Games and Paintability, ELECTRON J COMB vol. 23 (3) (2016), 12

203.

Mikkel Abrahamsen, Bartosz Walczak

Outer common tangents and nesting of convex hulls in linear time and constant workspace vol. 57 of Leibniz International Proceedings in Informatics (2016), "24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

202.

Adam Karczmarz, Jakub Łącki, Adam Polak, Jakub Radoszewski, Jakub Onufry Wojtaszczyk

Distributed Tasks: Introducing Distributed Computing to Programming Competitions, OLYMPIADS IN INFORMATICS vol. 10 (2016), 177-194

201.

Adam Polak

Counting Triangles in Large Graphs on GPU, 2016 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW) (2016), 740-746

200.

Bartłomiej Bosek, Jarosław Grytczuk, Paweł Rzążewski, Sebastian Czerwiński

Harmonious coloring of uniform hypergraphs, APPL ANAL DISCR MATH vol. 10(1) (2016), 73-87

199.

Marcin Kozik

Weak consistency notions for all CSPs of bounded width, PROCEEDINGS OF THE 31ST ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS'16) (2016), 633-641

198.

Libor Barto, Marcin Kozik

Robustly Solvable Constraint Satisfaction Problems, SIAM J COMPUT vol. 45(4) (2016), 1646–1669

197.

Kolja Knauer, Bartosz Walczak

Graph drawings with one bend and few slopes vol. 9644 of Lecture Notes in Computer Science (2016), "LATIN 2016: Theoretical Informatics, 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings", Springer

196.

Jakub Kozik, Dmitry A. Shabanov

Improved algorithms for colorings of simple hypergraphs and applications, J COMB THEORY B vol. Volume 116 (2016), 312-332

195.

Jakub Kozik

Multipass greedy coloring of simple uniform hypergraphs, RANDOM STRUCT ALGOR vol. Volume 48, Issue 1 (2016), 125-146

194.

János Pach, Bartosz Walczak

Decomposition of multiple packings with subquadratic union complexity, COMB PROBAB COMPUT vol. 25 (2016), 145-153

193.

Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc

A natural counting of lambda terms, LECTURE NOTES IN COMPUTER SCIENCE vol. 9587 (2016), 183-194

192.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych

Shortest Augmenting Paths for Online Matchings on Trees, LECTURE NOTES IN COMPUTER SCIENCE vol. 9499 (2016), 59-71

191.

Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang

Tree-width and dimension, COMBINATORICA vol. 36 (2016), 431-450

190.

Jarosław Grytczuk, Karol Kosiński, Michał Zmarz

Nonrepetitive colorings of line arrangements, EUR J COMBIN vol. 51 (2016), 275-279

189.

Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki

On the Duality of Semiantichains and Unichain Coverings, ORDER vol. 33(1) (2016), 29-38

2015

188.

Krzysztof Turowski

Optimal backbone coloring of split graphs with matching backbones, DISCUSSIONES MATHEMATICAE GRAPH THEORY vol. 35 (2015), 157-169

187.

Robert Janczewski, Krzysztof Turowski

The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones, INFORM PROCESS LETT vol. 115(2) (2015), 232-236

186.

Robert Janczewski, Krzysztof Turowski

The Backbone Coloring Problem for Bipartite Backbones, GRAPH COMBINATOR vol. 31(5) (2015), 1487-1496

185.

Robert Janczewski, Krzysztof Turowski

The computational complexity of the backbone coloring problem for planar graphs with connected backbones, DISCRETE APPL MATH vol. 184 (2015), 237-242

184.

Asymmetric coloring games on incomparability graphs vol. 49 of Electronic Notes in Discrete Mathematics (2015), "The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015", Elsevier Science

183.

Marcin Kozik, Joanna Ochremiak

Algebraic Properties of Valued Constraint Satisfaction Problem, PROCEEDINGS OF 42ND INTERNATIONAL COLLOQUIUM, ICALP 2015 (2015), 846-858

182.

Piotr Micek

On-line coloring between two lines vol. 34 of Leibniz International Proceedings in Informatics (2015), "31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

181.

Katarzyna Grygiel, Pierre Lescanne

Counting and generating terms in the binary lambda calculus, J FUNCT PROGRAM vol. 25 (2015), 25

180.

Andrew Suk, Bartosz Walczak

New bounds on the maximum number of edges in k-quasi-planar graphs, COMP GEOM-THEOR APPL vol. 50 (2015), 24-33

179.

Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak

On the Beer index of convexity and its variants vol. 34 of Leibniz International Proceedings in Informatics (2015), "31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands", Schloss Dagstuhl – Leibniz-Zentrum für Informatik

178.

Danila D. Cherkashin, Jakub Kozik

A note on random greedy coloring of uniform hypergraphs, RANDOM STRUCT ALGOR vol. 47 (2015), 407-413

177.

Libor Barto, Marcin Kozik, David Stanovský

Mal’tsev conditions, lack of absorption, and solvability, ALGEBR UNIV vol. 74 (2015), 185-206

176.

Marcin Kozik, Andrei Krokhin, Matthew Valeriote, Ross Willard

Characterizations of several Maltsev conditions, ALGEBR UNIV vol. 73 (2015), 205-224

175.

Jarosław Grytczuk, Karol Kosiński, Michał Zmarz

How to Play Thue Games, THEOR COMPUT SCI vol. 582 (2015), 83-88

174.

Zbigniew Jelonek, Michał Staromiejski

A note on locality of algebras, J ALGEBRA vol. 433 (2015), 231-242

173.

Andrzej Grzesik, Michał Morayne, Małgorzata Sulkowska

From directed path to linear order - the best choice problem for powers of directed path, SIAM J DISCRETE MATH vol. 29(1) (2015), 500-513

172.

Andrzej Grzesik, Mirjana Mikalački, Zoltán Lóránt Nagy, Alon Naor, Balázs Patkós, Fiona Skerman

Avoider-Enforcer star games, DISCRETE MATH THEOR vol. 17(1) (2015), 145-160

171.

Michał Dębski, Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak

The strong chromatic index of sparse graphs, INFORM PROCESS LETT vol. 115 (2015), 326–330

170.

Jarosław Grytczuk, Wojciech Lubawski

Splitting Multidimensional Necklaces and Measurable Colorings of Euclidean Spaces, SIAM J DISCRETE MATH vol. 29 (2015), 252–258

169.

Bartłomiej Bosek, Tomasz Krawczyk

A subexponential upper bound for the on-line chain partitioning problem, COMBINATORICA vol. 35 (2015), 1-38

168.

Maciej Bendkowski, Katarzyna Grygiel, Marek Zaionc

Asymptotic properties of combinatory logic, LECTURE NOTES IN COMPUTER SCIENCE vol. 9076 (2015), 62-72

167.

Minors and dimension, (2015), "26th Annual ACM-SIAM Symposium on Discrete Algorithms, January 4-6, 2015, San Diego, California, USA", Society for Industrial and Applied Mathematics (SIAM)

166.

Triangle-free geometric intersection graphs with no large independent sets, DISCRETE COMPUT GEOM vol. 53 (2015), 221-225

165.

Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak

Coloring triangle-free rectangle overlap graphs with O(log log n) colors, DISCRETE COMPUT GEOM vol. 53 (2015), 199-220

164.

Roman Glebov, Andrzej Grzesik, Tereza Klimošová, Daniel Král

Finitely forcible graphons and permutons, J COMB THEORY B vol. 110 (2015), 112-135

2014

163.

Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems, LECTURE NOTES IN COMPUTER SCIENCE vol. 8634 (Springer) (2014), 535--546

162.

Local-to-Global Consistency Implies Tractability of Abduction. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence., PROCEEDINGS OF THE TWENTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE (2014), 1128--1134

161.

Manuel Bodirsky, Hubie Chen, Michał Wrona

Tractability of quantified temporal constraints to the max, INT J ALGEBR COMPUT vol. 24 (2014), 1141--1156

160.

Katarzyna Grygiel, Pierre Lescanne

Counting Terms in the Binary Lambda Calculus, DMTCS PROCEEDINGS - 25TH INTERNATIONAL CONFERENCE ON PROBABILISTIC, COMBINATORIAL AND ASYMPTOTIC METHODS FOR THE ANALYSIS OF ALGORITHMS vol. DMTCS-HAL Proceedings Series (2014), 13

159.

Grzegorz Herman

Complexity of Cover-Preserving Embeddings of Bipartite Orders into Boolean Lattices, REPORTS ON MATHEMATICAL LOGIC (2014), 99-117

158.

Piotr Micek, Veit Wiechert

An on-line competitive algorithm for coloring P_8-free bipartite graphs, (2014), "Algorithms and Computation -- 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings", Springer

157.

Grzegorz Gutowski, Jakub Kozik, Piotr Micek, Xuding Zhu

Lower bounds for on-line graph colorings vol. 8889 (Lecture Notes in Computer Science) (2014), "Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings", Springer

156.

Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt

Making octants colorful, and related covering decomposition problems, (2014), "Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)", Society for Industrial and Applied Mathematics (SIAM)

155.

Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt

Making octants colorful, and related covering decomposition problems, SIAM J DISCRETE MATH vol. 28-4 (2014), 1948-1959

154.

Libor Barto, Marcin Kozik

Constraint Satisfaction Problems Solvable by Local Consistency Methods, J ACM vol. 61 (2014), article no. 3

153.

Anetta Górnicka, Joanna Grygiel, Katarzyna Grygiel

A note on blocks of skeleton tolerances, ACTA MATH HUNG vol. 143(1) (2014), 176-184

152.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych

Online bipartite matching in offline time, (2014), "55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, October 18-21, 2014, Philadelphia, PA, USA", Institute of Electrical and Electronics Engineers (IEEE)

151.

Andrzej Grzesik, Hrant Khachatrian

Interval edge-colorings of K_{1,m,n}, DISCRETE APPL MATH vol. 174 (2014), 140-145

150.

Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak

Coloring intersection graphs of arc-connected sets in the plane, DISCRETE COMPUT GEOM vol. 52 (2014), 399-415

149.

Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak

An extremal problem on crossing vectors, J COMB THEORY A vol. 128 (2014), 41-55

148.