View:

- no detail
- some detail
- full detail

## COMPLEXITY OF GRAPH POLYNOMIALS

*Steven D. Noble*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0013
- Subject:
- Mathematics, Probability / Statistics

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, ... More

## CONNECTIONS TO APPROXIMATION ALGORITHMS

*Rolf Niedermeier*

### in Invitation to Fixed-Parameter Algorithms

- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0014
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility ... More

## The Deep Question: P vs. NP

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0006
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter considers the consequences of the possibility that P is equal to NP. It examines why it is extremely difficult to prove that P is not equal to NP by focusing on a set of ‘metatheorems’ ... More

## Optimization and Approximation

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and ... More

## Randomized Algorithms

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0010
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

Certain situations require a random rather than a deterministic strategy. With a random strategy, the choices are unpredictable and the adversary may be kept off balance. This chapter focuses on the ... More

## Counting, Sampling, and Statistical Physics

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0013
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

The objects that are solutions to an NP-complete problem are difficult to count. Counting can be a subtle and complex problem even when the corresponding existence and optimisation problems are in P. ... More

## Computing complex zeros of polynomials and power series

*Jean-Marc Couveignes*

### in Computational Aspects of Modular Forms and Galois Representations: How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime (AM-176)

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0005
- Subject:
- Mathematics, Number Theory

The purpose of this chapter is twofold. First, it will prove two theorems (5.3.1 and 5.4.2) about the complexity of computing complex roots of polynomials and zeros of power series. The existence of ... More

## Computing <i>V<sub>f</sub></i> modulo <i>p</i>

*Jean-Marc Couveignes*

### in Computational Aspects of Modular Forms and Galois Representations: How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime (AM-176)

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0013
- Subject:
- Mathematics, Number Theory

This chapter addresses the problem of computing in the group of lsuperscript k-torsion rational points in the Jacobian variety of algebraic curves over finite fields, with an application to computing ... More

## The Winner Determination Problem

*Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm*

### in Combinatorial Auctions

- Published in print:
- 2005
- Published Online:
- August 2013
- ISBN:
- 9780262033428
- eISBN:
- 9780262302920
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033428.003.0013
- Subject:
- Society and Culture, Technology and Society

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical ... More

## Computational Aspects of Modular Forms and Galois Representations: How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime (AM-176)

*Bas Edixhoven and Jean-Marc Couveignes (eds)*

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- book

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.001.0001
- Subject:
- Mathematics, Number Theory

Modular forms are tremendously important in various areas of mathematics, from number theory and algebraic geometry to combinatorics and lattices. Their Fourier coefficients, with Ramanujan's ... More

## Introduction, main results, context

*Bas Edixhoven*

### in Computational Aspects of Modular Forms and Galois Representations: How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime (AM-176)

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0001
- Subject:
- Mathematics, Number Theory

This chapter provides an introduction to the subject, precise statements of the main results, and places these in a somewhat wider context. Topics discussed include statement of the main results, ... More

## Computing the residual Galois representations

*Bas Edixhoven*

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0014
- Subject:
- Mathematics, Number Theory

This chapter proves the main result on the computation of Galois representations. It provides a detailed description of the algorithm and a rigorous proof of the complexity. It first combines the ... More

## Seymour's Decomposition Theorem

*James Oxley*

### in Matroid Theory

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.003.0014
- Subject:
- Mathematics, Educational Mathematics

The excluded-minor theorem provides one characterization of the class of regular matroids. This chapter presents a different characterization of this class: a decomposition theorem for members of the ... More

## Spectral Methods for Dimensionality Reduction

*Saul Lawrence K., Weinberger Kilian Q., Sha Fei, Ham Jihun, and Lee Daniel D.*

### in Semi-Supervised Learning

- Published in print:
- 2006
- Published Online:
- August 2013
- ISBN:
- 9780262033589
- eISBN:
- 9780262255899
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033589.003.0016
- Subject:
- Computer Science, Machine Learning

This chapter provides an overview of unsupervised learning algorithms that can be viewed as spectral methods for linear and nonlinear dimensionality reduction. Spectral methods have recently emerged ... More

View:

- no detail
- some detail
- full detail