Stas Busygin's Home Page

Selected writings

• A New Trust Region Technique for the Maximum Weight Clique Problem, Discrete Applied Mathematics 154(15) (International Symposium on Combinatorial Optimization CO'02), pp. 2080-2096, 2006.
• On NP-hardness of the clique partition -- independence number gap recognition and related problems, Discrete Mathematics 304(4), pp. 460-463, 2006 (with D.V. Pasechnik, see also ECCC Report TR03-052).
• The SAT01 framework for NP problems, 2003.
• A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics, 2002.

Software

• QUALEX-MS: QUick ALmost EXact Maximum Weight Clique/Independent Set Solver based on the Motzkin-Straus QP formulation.
• theta-weighted-dimacs computes the (weighted) Lovasz number (theta function) of a graph given in the text or binary DIMACS format.
• JacMat: Jacobson-Matthews random Latin square generator.
• AntiSM: generator of graphs hard for greedy maximum clique heuristics (described in this paper.)
• VS: creates a vertex-saturated digraph from a given undirected graph.

Algebraic studies for P vs NP

Visit this group

Useful and interesting links

• Slashdot, News for Nerds, Stuff That Matters.
• Wilmott, Quantitative finance news, forums, blogs, wiki, etc.
• Eric Weisstein's World of Mathematics, the most comprehensive math reference library.
• The OpenScience Project, writing and releasing free and Open Source scientific software.
• comp.theory FAQ, frequently asked questions about CS theory.
• The Complexity Zoo, definitions, results, and references for about 500 complexity classes.
• Second DIMACS Challenge on clique, coloring, satisfiability.
• Netlib, a collection of mathematical software, papers, and databases.
• GAMS, a guide to available math software.
• Decision Tree for Optimization Software, a catalogue of optimization software.
• The Stony Brook Algorithm Repository, well-known algorithms and solvers.
• Computability and Complexity, an online course on complexity.
• INFORMS OR/MS Resources, former Mike Trick's OR page.
• A compendium of NP optimization problems, such problems known today.
• OR-Library, test instances of various optimization problems.
• SATLIB - The Satisfiability Library, a site for the satisfiability problem.
• SAT Live! Up-to-date links for the SATisfiability problem.
• TSPLIB, Travelling Salesman, Hamilton Cycle and other related instances.
• The Hamiltonian Page, Pablo Moscato's page for HCP.
• Blackbox, a SAT technology planning system.
• Patterncraft Software, boolean satisfiability and reduction.
• nauty, a well-known graph isomorphism solver.
• Optimization Online, an e-Print site for the optimization community.
• ECCC, Electronic Colloquium on Computational Complexity.
• The Collection of Computer Science Bibliographies, lots references to CS papers.
• arXiv.org e-Print archive.
• CiteSeer Scientific Digital Library, plenty of papers, techreports and theses.
• NEOS Guide Optimization Tree, introductory stuff for all fields of optimization.
• Computer Science Tutorials, basic computer science concepts online.
• Applied Mathematics, a very clear text on linear algebra and related topics.
• Chee K. Yap, "Introduction to Complexity Classes", a text on P, NP, etc.
• Herbert Wilf's Home Page, online math and CS books.
• Optima, the newsletter of the Mathematical Programming Society.
• Statistical Data Mining Tutorials, by Andrew Moore, the director of Google Pittsburgh office.
• Computational Complexity Web Log by Lance Fortnow.
• Shtetl-Optimized, Scott Aaronson's blog on quantum computers and complexity.