The distance approach to approximate combinatorial counting

Alexander Barvinok, Alex Samorodnitsky

Type: Article

Publication Date: 2001-12-01

Citations: 7

DOI: https://doi.org/10.1007/s00039-001-8219-3

View Publication

Download PDF

Locations

arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF
Deep Blue (University of Michigan) - View - PDF
Geometric and Functional Analysis - View

Similar Works

Action	Title	Year	Authors
+	The Distance Approach to Approximate Combinatorial Counting	2000	Alexander Barvinok Alex Samorodnitsky
+	Random Weighting, Asymptotic Counting, and Inverse Isoperimetry	2003	Alexander Barvinok Alex Samorodnitsky
+	Random Weighting, Asymptotic Counting, and Inverse Isoperimetry	2003	Alexander Barvinok Alex Samorodnitsky
+ PDF Chat	Random weighting, asymptotic counting, and inverse isoperimetry	2007	Alexander Barvinok Alex Samorodnitsky
+	Approximate Counting	1995	Rajeev Motwani Prabhakar Raghavan
+	Simple set cardinality estimation through random sampling	2015	Marco Bressan Enoch Peserico Luca Pretto
+	Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond	2020	Anup Bhattacharya Sourav Chakraborty Arijit Ghosh Gopinath Mishra Manaswi Paraashar
+	Shattered Sets and the Hilbert Function.	2015	Shay Moran Cyrus Rashtchian
+	Shattered Sets and the Hilbert Function	2016	Shay Moran Cyrus Rashtchian
+	Shattered Sets and the Hilbert Function	2015	Shay Moran Cyrus Rashtchian
+	Minimum average distance subsets in the hamming cube	2002	André Kündgen
+	Simple set cardinality estimation through random sampling.	2015	Marco Bressan Enoch Peserico Luca Pretto
+	ON THE SIZE OF A MINIMAL VERTEX COVER IN A RANDOM SUBGRAPH OF THE n-CUBE	2009	Eduard Toman Martin Staněk
+	Applications of Random Algebraic Constructions to Hardness of Approximation	2021	Boris Bukh C. S. Karthik Bhargav Narayanan
+	Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search	2019	Thomas D. Ahle Jakob Bæk Tejs Knudsen
+	Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search	2019	Thomas D. Ahle Jakob Bæk Tejs Knudsen
+	The discrepancy method: randomness and complexity	2002	Bernard Chazelle
+	Partitioning into Sets of Bounded Cardinality	2009	Mikko Koivisto
+ PDF Chat	Approximate Set Union via Approximate Randomization	2020	Bin Fu Pengfei Gu Yuming Zhao
+ PDF Chat	Approximate set union via approximate randomization	2021	Bin Fu Pengfei Gu Yuming Zhao

Works That Cite This (6)

Action	Title	Year	Authors
+	Random Weighting, Asymptotic Counting, and Inverse Isoperimetry	2003	Alexander Barvinok Alex Samorodnitsky
+	Vertex Isoperimetric Inequalities for a Family of Graphs on Z^k	2012	Ellen Veomett A. J. Radcliffe
+ PDF Chat	Vertex Isoperimetric Inequalities for a Family of Graphs on $\mathbb{Z}^k$	2012	Ellen Veomett A. J. Radcliffe
+ PDF Chat	Random weighting, asymptotic counting, and inverse isoperimetry	2007	Alexander Barvinok Alex Samorodnitsky
+	The Edge-Isoperimetric Problem in $(\mathbb{N}^2,\infty)$	2012	Emmanuel Tsukerman
+	Random Weighting, Asymptotic Counting, and Inverse Isoperimetry	2003	Alexander Barvinok Alex Samorodnitsky

Works Cited by This (18)

Action	Title	Year	Authors
+ PDF Chat	Asymptotic Theory of Finite Dimensional Normed Spaces	1986	Vitali Milman Gideon Schechtman
+	The Markov chain Monte Carlo method: an approach to approximate counting and integration	1996	Mark Jerrum Alistair Sinclair
+ PDF Chat	On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents	1998	Anna Galluccio Martin Loebl
+ PDF Chat	Concentration of measure and isoperimetric inequalities in product spaces	1995	Michel Talagrand
+	A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries	2001	Mark Jerrum Alistair Sinclair Eric Vigoda
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+ PDF Chat	Computing Mixed Discriminants, Mixed Volumes, and Permanents	1997	Alexander Barvinok
+	A mildly exponential approximation algorithm for the permanent	1996	M. Jerrum U. Vazirani
+ PDF Chat	Approximate counting via random optimization	1997	Alexander Barvinok
+	The matching problem for bipartite graphs with polynomially bounded permanents is in NC	1987	Dima Yu. Grigoriev Marek Karpiński