215 citations
- Microsoft (United States)US8 papers
- Johns Hopkins UniversityUS4 papers
- Massachusetts Institute of TechnologyUS4 papers
- Tel Aviv UniversityIL3 papers
- University of California, BerkeleyUS3 papers
- University of ChicagoUS3 papers
- University of MichiganUS3 papers
- University of WashingtonUS3 papers
- Argonne National LaboratoryUS2 papers
- Institut national de recherche en sciences et technologies du numériqueFR2 papers
- Microsoft Research (India)IN2 papers
- Microsoft Research New England (United States)US2 papers
5 papers · 1 filter
Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point
Christian Borgs, Jennifer T. Chayes, Prasad Tetali
We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice Z^d - heat bath dynamics and the Swendsen-Wang algorithm - and prove that,…
Stochastic Simulation of Process Calculi for Biology
Andrew Phillips, Matthew Lakin, Loïc Paulevé
Biological systems typically involve large numbers of components with complex, highly parallel interactions and intrinsic stochasticity. To model this complexity, numerous programm…
Property Testing via Set-Theoretic Operations
Victor Chen, Madhu Sudan, Ning Xie
Given two testable properties and , under what conditions are the union, intersection or set-difference of these two properties also testable? We…
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Parikshit Gopalan, Adam Klivans, Raghu Meka
We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with…
The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach
Christian Borgs, Jennifer Chayes, Jian Ding +1
We propose a new class of game-theoretic models for network formation in which strategies are not directly related to edge choices, but instead correspond more generally to the exe…