181 citations
- Microsoft Research (United Kingdom)GB2 papers
- Australian National UniversityAU1 paper
- Board of the Swiss Federal Institutes of TechnologyCH1 paper
- Columbia UniversityUS1 paper
- Délégation Paris 6FR1 paper
- ETH ZurichCH1 paper
- IBM Research - AlmadenUS1 paper
- IIT@MITUS1 paper
- Institut de Mathématiques de Jussieu-Paris Rive GaucheFR1 paper
- MIT Computer Science and Artificial Intelligence LaboratoryUS1 paper
- RWTH Aachen UniversityDE1 paper
- Sorbonne UniversitéFR1 paper
11 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…
d-wave resonating valence bond states of fermionic atoms in optical lattices
Simon Trebst, Ulrich Schollwoeck, Matthias Troyer +1
We study controlled generation and measurement of superfluid d-wave resonating valence bond (RVB) states of fermionic atoms in 2D optical lattices. Starting from loading spatial an…
Edge coloring models and reflection positivity
Balazs Szegedy
Solving a conjecture of M. H. Freedman, L. Lovász and A. Schrijver we prove that a graph parameter is edge reflection positive and multiplicative if and only if it can be represent…
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…
Hiding Satisfying Assignments: Two are Better than One
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-…
Degree Distribution of Competition-Induced Preferential Attachment Graphs
N. Berger, C. Borgs, J. T. Chayes +2
We introduce a family of one-dimensional geometric growth models, constructed iteratively by locally optimizing the tradeoffs between two competing metrics, and show that this fami…