Hard problems on random graphs

DOI10.4230/LIPICS.ICALP.2020.40MaRDI QIDQ6842536zbMATH OpenFDO

Authors Jan Dreier, Henri Lotze, Peter Rossmanith

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.40

zbMATH Keywords

random graphsaverage-case complexityfirst-order model checking

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 1688350 (Why is no real title available?)
• scientific article; zbMATH DE number 1231233 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1962838 (Why is no real title available?)
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 3090153 (Why is no real title available?)
• scientific article; zbMATH DE number 7650219 (Why is no real title available?)
• Complexity of the first-order theory of almost all finite structures
• Fundamentals of parameterized complexity
• Model-Checking Problems as a Basis for Parameterized Intractability
• On the average-case complexity of parameterized clique
• On the categoricity in power of elementary deductive systems and some related problems
• On the theory of average case complexity
• Parameterized algorithms
• Parametrized complexity theory.
• Probabilities on finite models

This page was built for publication: Hard problems on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842536)