Skip to main content
improved language
Source Link
Juho
  • 3.2k
  • 2
  • 27
  • 36

implications Implications of Riemann Hypothesis variants in TCS

theThe over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants.

  I recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,

what are the major implications of the Riemann hypothesis in TCS?

(eg also so-called "bridge thms" etc.?) as As a start here is an example from a recent paper, Homomorphism Polynomials complete for VP /by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction:

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

implications of Riemann Hypothesis variants in TCS

the over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants.

  recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. wondering,

what are the major implications of the Riemann hypothesis in TCS?

(eg also so-called "bridge thms" etc.?) as a start here is an example from a recent paper, Homomorphism Polynomials complete for VP / Durand, Mahajan, Malod, de Rugy-Altherre, Saurab

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

Implications of Riemann Hypothesis variants in TCS

The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,

what are the major implications of the Riemann hypothesis in TCS?

As a start here is an example from a recent paper, Homomorphism Polynomials complete for VP by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction:

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

Tweeted twitter.com/#!/StackCSTheory/status/538939087559081984
Source Link
vzn
  • 11.1k
  • 2
  • 31
  • 67

implications of Riemann Hypothesis variants in TCS

the over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants.

recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. wondering,

what are the major implications of the Riemann hypothesis in TCS?

(eg also so-called "bridge thms" etc.?) as a start here is an example from a recent paper, Homomorphism Polynomials complete for VP / Durand, Mahajan, Malod, de Rugy-Altherre, Saurab

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).