The Library
Content-description interfaces for medical imaging
Tools
Ng, Chee Un and Martin, Graham R. (2001) Content-description interfaces for medical imaging. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF
WRAP_cs-rr-383.pdf - Published Version - Requires a PDF viewer. Download (504Kb) | Preview |
Abstract
Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. They considered the family of "cautious" ergodic Markov chains with uniform stationary distribution and showed that, for every fixed connected "nontrivial" graph H, every such chain mixes slowly. In this paper, we give a complexity result for the problem. Namely, we show that for any fixed graph H with no trivial components, there is unlikely to be any Polynomial Almost Uniform Sampler (PAUS) for H-colourings. We show that if there were a PAUS for the H-colouring problem, there would also be a PAUS for sampling independent sets in bipartite graphs and, by the self-reducibility of the latter problem, there would be a Fully-Polynomial Randomised Approximation Scheme (FPRAS) for #BIS - the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill and Jerrum have shown that #BIS is complete in a certain logically-defined complexity class. Thus, a PAUS for sampling H-colourings would give an FPRAS for the entire complexity class. In order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Content-based image retrieval, Diagnostic imaging | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | 20 August 2001 | ||||
Dates: |
|
||||
Number: | Number 383 | ||||
Number of Pages: | 29 | ||||
DOI: | CS-RR-384 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 28 July 2016 | ||||
Date of first compliant Open Access: | 28 July 2016 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year