An Average Case NP-complete Graph Colouring Problem

DOI10.1017/S0963548318000123zbMath1398.05090OpenAlexW3100067187MaRDI QIDQ4962593

Ramarathnam Venkatesan, Leonid A. Levin

Publication date: 5 November 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548318000123

zbMATH Keywords

random graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The development of the number field sieve
• Non-abelian analogs of lattice rounding
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Average case completeness
• The tale of one-way functions
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Lattice problems in NP ∩ coNP
• Average Case Complete Problems
• Expected Computation Time for Hamiltonian Path problem
• Random Graph Isomorphism
• Matrix Transformation Is Complete for the Average Case
• The NP-completeness column: An ongoing guide