About
Recent years have seen dramatic progress in counting complexity. In exact computation, we now have a complete classification of counting CSPs into those that are polynomial-time solvable and those that are hard for the complexity class #P. The past decade or so has also seen the emergence of a nascent complexity theory of approximate counting.
The aim of this workshop is to spur progress in this field. In exact computation, we would like to extend our study into models that are more general than CSPs or more refined (e.g., holants, also known as tensor networks, or as factor graphs). We will also examine the algorithmic effectiveness of classification criteria. For problems that are computationally intractable, we need to examine escape routes. Recent dichotomy theorems strongly suggest that holographic algorithms based on matchgates are a universal methodology for problems that are #P-hard in general but P-time computable over planar structures. This thesis is subject to refutation by on-going work. For approximate computation, the corresponding complexity theory is provisional, leaving several important problems unclassified, and needs to be developed. Where efficient approximation algorithms in the conventional sense do not exist, we should look for algorithms that provide weaker approximation guarantees, for example bounding the logarithm of the number of solutions.
The ultimate goal of this investigation is to shed light on the computational complexity of counting problems from domains such as the following: graph homomorphisms, constraint satisfaction problems, holants, combinatorial enumeration problems (generating functions), models from statistical physics (partition functions), graph polynomials and polynomials on more general structures.
All talks will be recorded. Enquiries may be sent to the organizers workshop_counting2 [at] lists.simons.berkeley.edu (at this address.)style="line-height: 1.57143em;"
Chairs/Organizers
Invited Participants
David Aldous (UC Berkeley), Alexander Barvinok (University of Michigan), Ivona Bezakova (Rochester Institute of Technology), Markus Bläser (Universität des Saarlandes), Michele Borassi (IMT), Cornelius Brand (Saarland University), Raimundo Briceño (University of British Columbia), Andrei Bulatov (Simon Fraser Universeity), Jin-Yi Cai (University of Wisconsin-Madison), Pietro Caputo (Roma Tre University), Xi Chen (Columbia University), Sitan Chen (Harvard University), Colin Cooper (King's College London), Radu Curticapean (Universität des Saarlandes), Victor Dalmau (Universitat Pompeu Fabra), Varsha Dani (University of New Mexico), Holger Dell (Universität des Saarlandes), Persi Diaconis (Stanford University), Martin Dyer (University of Leeds), Jo Ellis-Monaghan (Saint Michael's College), Funda Ergun (Indiana University), Graham Farr (Monash University), Laura Florescu (NYU), Fedor Fomin (University of Bergen), Alan Frieze (Carnegie Mellon University), Zhiguo Fu (University of Wisconsin-Madison), Peter Fulla (University of Oxford), Marylou Gabrié (École Normale Supérieure Paris), Andreas Galanis (University of Oxford), David Gamarnik (MIT), Leslie Ann Goldberg (University of Oxford), Frederic Green (Clark University), Heng Guo (Queen Mary, University of London), Mor Harchol-Balter (Carnegie Mellon University), Tom Hayes (University of New Mexico), Tyler Helmuth (UC Berkeley), Miki Hermann (Ecole Polytechnique), Steve Homer (Boston University), Mark Jerrum (Queen Mary, University of London), Ravi Kannan (Microsoft Research India), Marek Karpinski (University of Bonn), Florent Krzakala (École Normale Supérieure Paris), JM Landsberg (Texas A&M University), John Lapinskas (University of Oxford), Dick Lipton (Georgia Institute of Technology), Martin Loebl (Charles University), Pinyan Lu (Shanghai University of Finance and Economics), Meena Mahajan (Institute of Mathematical Sciences), Janos Makowsky (Technion-Israel Institute of Technology), Susan Margulies (United States Navel Academy), Andrea Montanari (Stanford University), Jason Morton (Pennsylvania State University), Emanuele Natale (Sapienza University of Rome), Jaroslav Nesetril (Charles University), Guus Regts (University of Amsterdam), David Richerby (University of Oxford), Marc Roth (Universität des Saarlandes), Alistair Sinclair (UC Berkeley), Allan Sly (UC Berkeley), Piyush Srivastava (California Institute of Technology), Nike Sun (Massachusetts Institute of Technology), Les Valiant (Harvard University), Mingji Xia (Institute of Software, Chinese Academy of Sciences), Jiaming Xu (University of Pennsylvania), Yitong Yin (Nanjing University), Lenka Zdeborova (Institut de Physique Théorique), Chihao Zhang (Shanghai Jiao Tong University), Standa Zivny (University of Oxford)