NDLI: Approximating the Permanent via Nonabelian Determinants

Please wait, while we are loading the content...

Approximating the Permanent via Nonabelian Determinants

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Moore, Cristopher Russell, Alexander
Copyright Year	2012
Abstract	Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671697], we have known that the permanent of a matrix with entries in $\{0,1\}$ can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra $\mathcal{A}$ and considering the determinant of the resulting matrix. In the case where $\mathcal{A}$ is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the firstand therefore the number of trials we need to obtain a good estimate of the permanentis $(1 + O(1/d))^n$ when $\mathcal{A}$ is the algebra of $d \times d$ matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constantthe only case in which an efficient algorithm is knownwe show that the critical ratio exceeds $2^{n} / n^{O(d)}$. Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group.
Starting Page	332
Ending Page	355
Page Count	24
File Format	PDF
ISSN	00975397
DOI	10.1137/100806709
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	41
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2012-04-17
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems Analysis of algorithms and problem complexity permanent approximation algorithm determinant
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximating the Permanent via Nonabelian Determinants

Hardness of Approximating the Closest Vector Problem with Pre-Processing

On Approximating Restricted Cycle Covers

Permanent versus determinant: not via saturations

Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment

The complexity of multiple-precision arithmetic

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

On Approximating Four Covering and Packing Problems

Approximating the Permanent via Nonabelian Determinants

Similar Documents

Approximating the Permanent via Nonabelian Determinants

Hardness of Approximating the Closest Vector Problem with Pre-Processing

On Approximating Restricted Cycle Covers

Permanent versus determinant: not via saturations

Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment

The complexity of multiple-precision arithmetic

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

On Approximating Four Covering and Packing Problems

Approximating the Permanent via Nonabelian Determinants