181 citations
- Johns Hopkins UniversityUS2 papers
- Microsoft (United States)US2 papers
- Australian National UniversityAU1 paper
- Berkeley CollegeUS1 paper
- Centrum Wiskunde & InformaticaNL1 paper
- Columbia UniversityUS1 paper
- Cornell UniversityUS1 paper
- Délégation Paris 6FR1 paper
- Institut de Mathématiques de Jussieu-Paris Rive GaucheFR1 paper
- Massachusetts Institute of TechnologyUS1 paper
- Sorbonne UniversitéFR1 paper
- UCLA HealthUS1 paper
4 papers · 1 filter
On computing the fixpoint of a set of boolean equations
Viktor Kuncak, K. Rustan M. Leino
This paper presents a method for computing a least fixpoint of a system of equations over booleans. The resulting computation can be significantly shorter than the result of iterat…
The Chromatic Number of Random Regular Graphs
Dimitris Achlioptas, Cristopher Moore
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k…
Reflection positivity, rank connectivity, and homomorphism of graphs
M. Freedman, L. Lovasz, A. Schrijver
It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflect…
The World Wide Telescope: An Archetype for Online Science
Jim Gray, Alexander S. Szalay
Most scientific data will never be directly examined by scientists; rather it will be put into online databases where it will be analyzed and summarized by computer programs. Scien…