- Due to multiple requests, the early registration deadline has been
extended to May 18.
- We recommend that participants make their hotel reservations as early as
possible since Paris is an attractive destination for tourists during the
summer.
- The conference programme is now available.
The 49th International Colloquium on Automata, Languages, and Programming
(ICALP) will take place
** in Paris, France, and online on 4-8 July 2022. **
The 2022 edition has the following special features:
- The conference is hybrid.
- This will be the 50th birthday of the conference and some special events
are
planned.
- The ICALP Extended Stay Support Scheme (IESSS) is here for helping the
organisation of collaborations around the conference.
ICALP is the main conference and annual meeting of the European Association
for
Theoretical Computer Science (EATCS). As usual, ICALP will be preceded by a
series of workshops, which will take place on July 4.
The 2022 edition will be also the occasion to celebrate the 50th
anniversary of
both EATCS and the first ICALP, which was first held in 1972 in
Rocquencourt,
in the Paris area.
============= Important dates and information =============
Website: https://icalp2022.irif.fr/
Early Registration: May 18
Conference: July 4-8, 2022
Workshops: July 4
============= Registration =============
For registration, follow this link: https://icalp2022.irif.fr/?page_id=50
============= Extended Stay Support Scheme (IESS) =============
For its 49th edition, the ICALP conference offers to its attendees an
Extended
Stay Support Scheme (IESSS) aiming at enhancing scientific collaborations
and
diminishing the carbon footprint of scientific research activities. ICALP
2022
attendees are encouraged to combine their visit to Paris with collaborations
with local researchers.
This support scheme is primarily intended for participants travelling long
distances and must be combined with an attendance to ICALP. Upon
acceptation,
research institutes involved in this mechanism will cover standard expenses
(accommodation and traveling fees, plane excluded) and will provide
material
support for research activities.
See https://icalp2022.irif.fr/?page_id=50 for more information.
============= Invited Speakers =============
Albert Atserias, Universitat Politècnica de Catalunya
Constantinos Daskalakis, MIT
Leslie Ann Goldberg, Oxford University
Madhu Sudan, Harvard
Stéphan Thomassé, ENS Lyon
Santosh Vempala, Georgia Tech
============= Awards =============
During the conference, the following awards will be given:
- the EATCS award (https://eatcs.org/index.php/eatcs-award),
- the Gödel prize (https://eatcs.org/index.php/goedel-prize),
- the Presburger award (https://eatcs.org/index.php/presburger),
- the EATCS distinguished dissertation award
(https://eatcs.org/index.php/dissertation-award),
- the best papers for Track A and track B,
- the best student papers for Track A and track B.
============= Accepted papers =============
See https://icalp2022.irif.fr/?page_id=85
<https://icalp2022.irif.fr/?page_id=85>
============= Workshops =============
See https://icalp2022.irif.fr/?page_id=46 for more information.
- Parameterized Approximation Algorithms Workshop
- Combinatorial Reconfiguration
- Recent Advances on Total Search Problems
- Algorithmic Aspects of Temporal Graphs V
- Trends in Arithmetic Theories
- Structure Meets Power 2022
- Straight-Line Programs, Word Equations and their Interplay
- Graph Width Parameters: from Structure to Algorithms
============= Programme =============
See
https://icalp2022.irif.fr/wp-content/uploads/2022/05/icalp2022programme.pdf
<https://icalp2022.irif.fr/wp-content/uploads/2022/05/icalp2022programme.pdf.>
or below.
# Tuesday 8h30-9h30. Invited speaker 1
* Santosh Vempala
_The Manifold Joys of Sampling in High Dimension_
# Tuesday 10h00-12h05. Paper session 1
## Graph algorithms
* Sebastian Forster, and Tijn de Vos
_Faster Cut Sparsification of Weighted Graphs_
* Tianyi Zhang
_Faster Cut-Equivalent Trees in Simple Graphs_
* Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska
Williams, and Ziqian Zhong
_New Additive Approximations for Shortest Paths and Cycles_
* Caroline Brosse, Vincent Limouzy, and Arnaud Mary
_Polynomial Delay Algorithm for Minimal Chordal Completions_
* Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin
Pilipczuk, Paweł Rzążewski, and Marek Sokołowski
_Max Weight Independent Set in Fraphs with no Long Claws: An Analog of the
Gyárfás' Path Argument_
## Games and verification
* Léonard Brice, Jean-Francois Raskin, and Marie Van Den Bogaard
_The complexity of SPEs in Mean-payoff Games_
* Benjamin Bordais, Damien Busatto-Gaston, Shibashis Guha, and
Jean-Francois Raskin
_Strategy Synthesis for Global Window PCTL_
* Hugo Gimbert, Corto Mascle, Anca Muscholl, and Igor Walukiewicz
_Distributed Controller Synthesis for Deadlock Avoidance_
* Xavier Allamigeon, Stephane Gaubert, Ricardo D. Katz, and Mateusz Skomra
_Universal Complexity Bounds Based on Value Iteration and Application to
Entropy Games_
* Nathalie Bertrand, Nicolas Markey, Ocan Sankur, and Nicolas Waldburger
_Parameterized Safety Verification of Round-based Shared-memory Systems_
## Sketching and streaming
* Aviad Rubinstein, and Junyao Zhao
_Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond
1/2-Approximation_
* Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico
Zenklusen
_Streaming Submodular Maximization under Matroid Constraints_
* Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý
_Streaming Algorithms for Geometric Steiner Forest_
* Moses Charikar, and Erik Waingarten
_Polylogarithmic Sketches for Clustering_
* Amit Deshpande, and Rameshwar Pratap
_One-pass Additive-error Subset Selection for $\ell_{p}$ Subspace
approximation_
## Coding theory
* Tal Yankovitz, and Gil Cohen
_LCC and LDC: Tailor-made Distance Amplification and a Refined Separation_
* Nicolas Resch, and Chen Yuan
_Threshold Rates of Code Ensembles: Linear is Best_
* Dean Doron, and Mary Wootters
_High-Probability List-Recovery, and Applications to Heavy Hitters_
* Ittai Rubinstein
_Explicit and Efficient Construction of (nearly) Optimal Rate Codes for the
Binary Deletion Channel and the Poisson Repeat Channel_
* Zhenjian Lu, Igor Oliveira, and Marius Zimand
_Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity_
# Tuesday 14h00-15h00. Invited speaker 2
* Leslie Ann Goldberg
_Some new (and old) Results on Contention Resolution_
# Tuesday 15h30-17h10. Paper session 2
## Quantum
* Chi-Ning Chou, Peter Love, Jonathan Shi, and Juspreet Singh Sandhu
_Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond_
* Penghui Yao, Yitong Yin, and Xinyuan Zhang
_Polynomial-Time Approximation of Zero-Free Partition Functions_
* Jaikumar Radhakrishnan, Shyam Dhamapurkar, and Shubham Pawar
_Set Membership with Two Classical and Quantum Bit Probes_
* Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar
_Separations between Combinatorial Measures for Transitive Functions_
## Computability and dynamic systems
* Djamel Eddine Amir, and Mathieu Hoyrup
_Computability of Finite Simplicial Complexes_
* Donald Stull
_The Dimension Spectrum Conjecture for Planar Lines_
* Ville Salo, and Ilkka Törmä
_What can Oracles Teach us about the Ultimate Fate of Life?_
* Jakob Piribauer, Ocan Sankur, and Christel Baier
_The Variance-penalized Stochastic Shortest Path Problem_
## Reconstruction problems
* Josep Diaz, Varsha Dani, Cristopher Moore, and Thomas Hayes
_Improved Reconstruction of Random Geometric Graphs_
* Andrew McGregor, and Rik Sengupta
_Graph Reconstruction from Random Subgraphs_
* Akash Kumar, Anand Louis, and Rameesh Paul
_Exact Recovery Algorithm for Planted Bipartite Graph in Semi-random Graphs_
* Guy Blanc, Jane Lange, and Li-Yang Tan
_Reconstructing Decision Trees_
## Game theory, networks, and distributed
* William Kuszmaul, and Shyam Narayanan
_Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game_
* Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, and Nicole
Wein
_Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost_
* Stavros Ioannidis, Bart de Keijzer, and Carmine Ventre
_Strong Approximations and Irrationality in Financial Networks with
Derivatives_
* Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko
_Social Distancing Network Creation_
# Tuesday 18h00-21h00. Cocktail and vernissage of the exhibition for the 50
years of EATCS / ICALP
# Wednesday 8h30-9h30. Invited speaker 3
* Constantinos Daskalakis
_Equilibrium Computation, Deep Learning, and Multi-Agent (Reinforcement)
Learning_
# Wednesday 10h00-12h05. Paper session 3
## Counting and sampling
* Charilaos Efthymiou
_On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and
Hypergraphs._
* Ivona Bezakova, Andreas Galanis, Leslie Goldberg, and Daniel Stefankovic
_Fast sampling via Spectral Independence beyond Bounded-degree Graphs_
* Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli
Ravelomanana, Daniel Stefankovic, and Eric Vigoda
_Metastability of the Potts Ferromagnet on Random Regular Graphs_
* Andreas Galanis, Daniel Stefankovic, and Eric Vigoda
_Approximating Observables is as Hard as Counting_
* Guoliang Qiu, Yanheng Wang, and Chihao Zhang
_A Perfect Sampler for Hypergraph Independent Sets_
## Tranducers and automata
* Mika Göös, Stefan Kiefer, and Weiqiang Yuan
_Lower Bounds for Unambiguous Automata via Communication Complexity_
* Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen
_On the Size of Good-for-games Rabin Automata and its Link with the Memory
in Muller Games_
* Léo Exibard, Emmanuel Filiot, and Ayrat Khalimov
_A Generic Solution to Register-bounded Synthesis With an Application to
Discrete Orders_
* Leon Bohn, and Christof Löding
_Passive Learning of Deterministic Büchi Automata by Combinations of DFAs_
* Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and
Georg Zetzsche
_Reachability in Bidirected Pushdown VASS_
## Property testing
* Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen
_Tolerant Bipartiteness Testing in Dense Graphs_
* Louis Esperet, and Sergey Norin
_Testability and Local Certification of Monotone Properties in Minor-closed
Classes_
* Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten
_Finding Monotone Patterns in Sublinear Time, Adaptively_
* Talya Eden, Dana Ron, and Will Rosenbaum
_Almost Optimal Bounds for Sublinear-Time Sampling of $k$-Cliques in
Bounded Arboricity Graphs_
* Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos
_Improved Sublinear-Time Edit Distance for Preprocessed Strings_
## Dynamic algorithms and sensitivity oracles
* Josh Alman, and Dean Hirsch
_Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior
Algebras_
* Surender Baswana, Koustav Bhanja, and Abhyuday Pandey
_Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle_
* Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin
Schirneck
_Deterministic Sensitivity Oracles for Diameter, Eccentricities and All
Pairs Distances_
* Aaron Bernstein, Jan van den Brand, Maximilian Probst, Danupon Nanongkai,
Thatchaphol Saranurak, Aaron Sidford, and He Sun
_Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary_
* Aleksander B. G. Christiansen, and Eva Rotenberg
_Fully-dynamic α + 2 Arboricity Decomposition and Implicit Colouring._
# Wednesday 14h00-16h05. Best papers session
* Joakim Blikstad
_Sublinear-round Parallel Matroid Intersection_
* Jakub Tětek
_Approximate Triangle Counting via Sampling and Fast Matrix Multiplication_
* Gaëtan Douéneau-Tabot
_Hiding Pebbles when the Output Alphabet is Unary_
* Ilan Newman, and Nithin Varma
_Strongly Sublinear Algorithms for Testing Pattern Freeness_
* Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon
Toruńczyk
_Twin-width and Types_
# Wednesday 16h45-17h30. EATCS Award 2022
* TBA
_TBA_
# Wednesday 17h30-19h30. EATCS general assembly
*
_EATCS general assembly:\\ EATCS fellows, EATCS distinguished dissertation
Award, Best Icalp papers, Best Icalp Student Papers_
# Thursday 8h30-9h30. Invited speaker 4
* Albert Atserias
_Towards a Theory of Algorithmic Proof Complexity: Motivation and
Directions_
# Thursday 10h00-12h05. Paper session 4
## Computational Geometry
* Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese
_Tight Approximation Algorithms for Two-dimensional Guillotine Strip
Packing_
* Fedor Fomin, Petr Golovach, Tanmay Inamdar, and Meirav Zehavi
_(Re)packing Equal Disks into Rectangle_
* Ziyun Huang, and Jinhui Xu
_In-Range Farthest Point Queries and Related Problem in High Dimensions_
* Jacobus Conradi, and Anne Driemel
_On Computing the k-Shortcut Fréchet Distance_
* Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas
_A PTAS for Packing Hypercubes into a Knapsack_
## Parameterized complexity
* Ramanujan M. Sridharan, Daniel Lokshtanov, and Fahad Panolan
_Backdoor Sets on Nowhere Dense SAT_
* Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang
_On Lower Bounds of Approximating Parameterized $k$-Clique_
* Ishay Haviv
_A Fixed-Parameter Algorithm for the Kneser Problem_
* Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer
_Parameterized Complexity of Untangling Knots_
* Alexandra Lassota, Aleksander Łukasiewicz, and Adam Polak
_Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in
Multigraphs_
## Approximation algorithms
* Lin Chen, Xiaoyu Wu, and Guochuan Zhang
_Approximation Algorithms for Interdiction Problem with Packing Constraints_
* Karl Bringmann, and Alejandro Cassis
_Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution_
* Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi
_Improved Approximation Algorithms and Lower Bounds for
Search-Diversification Problems_
* Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas
_Near-optimal Algorithms for Stochastic Online Bin Packing_
* Claire Mathieu, and Hang Zhou
_A PTAS for Capacitated Vehicle Routing on Trees_
## Optimization
* Shunhua Jiang, Bento Natura, and Omri Weinstein
_A Faster Interior-Point Method for Sum-of-Squares Optimization_
* Ming Ding, Rasmus Kyng, and Peng Zhang
_Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear
Time Reductions_
* Marcin Briański, Martin Koutecký, Daniel Kráľ, Kristýna Pekárková, and
Felix Schröder
_Characterization of Matrices with Bounded Graver Bases and Depth
Parameters and Applications to Anteger Programming_
* Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang
_Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear
Equation Complete Gadgets_
* Mitchell Black, and Amir Nayyeri
_Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial
Complexes_
# Wednesday 14h30-15h50. Presburger Award and Gödel Prize 2022
* TBA
_TBA_
* TBA
_TBA_
# Thursday 16h00-17h40. Paper session 5
## Homomorphisms
* Martin Grohe, Gaurav Rattan, and Tim Seppelt
_Homomorphism Tensors and Linear Equations_
* Sandra Kiefer, and Daniel Neuen
_A Study of Weisfeiler-Leman Colorings on Planar Graphs_
* Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and
Kirill Simonov
_The Fine-Grained Complexity of Graph Homomorphism Parameterized by
Clique-Width_
* Balagopal Komarath, Anurag Pandey, and C. S. Rahul
_Monotone Arithmetic Complexity of Graph Homomorphism Polynomials_
## Process calculi and types
* David Barozzini, Paweł Parys, and Jan Wróblewski
_Unboundedness for Recursion Schemes: A Simpler Type System_
* Enguerrand Prebet
_Functions and References in the pi-Calculus: Full Abstraction and Proof
Techniques_
* Todd Schmid, Wojciech Rozowski, Alexandra Silva, and Jurriaan Rot
_Processes Parametrised by an Algebraic Theory_
## Learning theory, fairness, and privacy
* Jan Pich, and Rahul Santhanam
_Learning Algorithms versus Automatability of Frege Systems_
* Nathaniel Harms, and Yuichi Yoshida
_Downsampling for Testing and Learning in Product Distributions_
* Niclas Boehmer, and Tomohiro Koana
_The Complexity of Finding Fair Many-to-One Matchings_
* Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee
_Privately Estimating Graph Parameters in Sublinear time_
## Randomness in computation
* Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João
Ribeiro
_Low-Degree Polynomials Extract from Local Sources_
* Shir Peleg, Gil Cohen, Dor Minzer, Aaron Potechin, and Amnon Ta-Shma
_Expander Random Walks: The General Case and Limitations_
* Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha
_Smoothed Analysis of the Koml\'os Conjecture_
* Jakob Bæk Tejs Houen, and Mikkel Thorup
_Understanding the Moments of Tabulation Hashing via Chaoses_
# Friday 8h30-9h30. Invited speaker 5
* Madhu Sudan
_Streaming and Sketching Complexity of CSPs: A survey_
# Friday 10h00-12h05. Paper Session 6
## Data structures, sorting, and string processing
* Elahe Ghasemi, Vincent Jugé, and Ghazal Khalighinejad
_Galloping in Fast-growth Natural Merge Sorts_
* Takaaki Nishimoto, Shunsuke Kanda, and Yasuo Tabei
_An Optimal-Time RLBWT Construction in BWT-runs Bounded Space_
* Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan
_Fully Functional Parameterized Suffix Trees in Compact Space_
* Debarati Das, Tomasz Kociumaka, and Barna Saha
_Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding_
* Pawel Gawrychowski, and Karol Pokorski
_Sublinear Dynamic Interval Scheduling (on one or multiple machines)_
## Graphs and complexity
* Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma,
and Raghunath Tewari
_Dynamic Meta-theorems for Distance and Matching_
* Amina Doumane
_Regular Expressions for Tree-Width 2 Graphs_
* Tamio-Vesa Nakajima, and Stanislav Živný
_Linearly Ordered Colourings of Hypergraphs_
* Niel De Beaudrap, Aleks Kissinger, and John van de Wetering
_Circuit Extraction for ZX-diagrams can be \#P-hard_
* Pawel Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß
_Satisfiability Problems for Finite Groups_
## Graph distances and fault tolerance
* Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary
_Pairwise Reachability Oracles and Preservers under Failures_
* Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon
Toruńczyk, and Alexandre Vigny
_Algorithms and Data Structures for First-order Logic with Connectivity
under Vertex Failures_
* Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang
_Almost Tight Approximation Hardness for Single-Source Directed
k-Edge-Connectivity_
* Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol
Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai
_Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time
LP Solver_
* Shimon Kogan, and Merav Parter
_Beating Matrix Multiplication for $n^{1/3}$-Directed Shortcuts_
## Complexity
* Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann
_A Structural Investigation of the Approximability of Polynomial-Time
Problems_
* Theodoros Papamakarios, and Alexander Razborov
_Space Characterizations of Complexity Measures and Size-space Trade-offs
in Propositional Proof Systems_
* Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu
_The SDP Value of Random 2CSPs_
* Luyining Gan, and Jie Han
_The Decision Problem for Perfect Matchings in Dense Hypergraphs_
* David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie
_Unique Assembly Verification in Two-Handed Self-Assembly_
# Thursday 19h30-22h30. Conference dinner
# Friday 14h00-15h00. Invited speaker 6
* Stéphan Thomassé
_TBA_
# Friday 15h30-16h45. Paper session 7
## Online algorithms
* Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou
_Competitive Vertex Recoloring_
* Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh
_Online Weighted Cardinality Joint Replenishment Problem with Delay_
## Decremental algorithms
* Jakub Łącki, and Yasamin Nazari
_Near-Optimal Decremental Hopsets with Applications_
* Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian
_Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching_
* Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja
_Decremental Matching in General Graphs_
## Cryptography
* Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta
_Factoring and Pairings are not Necessary for iO: Circular-Secure LWE
Suffices_
* Shweta Agrawal, Damien Stehle, and Anshu Yadav
_Round-Optimal Lattice-Based Threshold Signatures, Revisited_
* Justin Holmgren, Andrea Lincoln, and Ron Rothblum
_Delegation for Search Problems_
## Counting and complexity
* Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu
_Listing, Verifying and Counting Lowest Common Ancestors in DAGs:
Algorithms and Fine-Grained Lower Bounds_
* Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang
_Counting and Enumerating Optimum Cut Sets for Hypergraph $k$-partitioning
problems for fixed $k$_
* Pierre Bergé, Édouard Bonnet, and Hugues Déprés
_Deciding Twin-width at most 4 is NP-complete_
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
