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
9 papers
Every decision tree has an influential variable
Ryan O'Donnell, Michael Saks, Oded Schramm +1
We prove that for any decision tree calculating a boolean function , \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where is the probability that the…
A probabilistic approach to the geometry of the \ell_p^n-ball
Franck Barthe, Olivier Guedon, Shahar Mendelson +1
This article investigates, by probabilistic methods, various geometric questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms of independent random variabl…
Sequential File Programming Patterns and Performance with .NET
Peter Kukol, Jim Gray
Programming patterns for sequential file access in the .NET Framework are described and the performance is measured. The default behavior provides excellent performance on a single…
Scientific Data Management in the Coming Decade
Jim Gray, David T. Liu, Maria Nieto-Santisteban +3
This is a thought piece on data-intensive science requirements for databases and science centers. It argues that peta-scale datasets will be housed by science centers that provide…
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…