# Questions tagged [algebraic-complexity]

The tag has no usage guidance.

74 questions
Filter by
Sorted by
Tagged with
3k views

### Mulmuley's GCT program

It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
3k views

### Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
2k views

### Integer multiplication when one integer is fixed

$n$ is a parameter in the problem. For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$. Problem: Given $n$ what is the complexity of ...
1k views

### Complexity of testing for a value versus computing a function

In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example: Evaluating the ...
2k views

### Sum-of-squares proof system

Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares. Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting? ...
607 views

279 views

### Straight line complexity of monomials

Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$ we define $L(f)$ to be the straight-line complexity of $f$ over $k$. Let $F$ be the set of monomials of $f$, namely the ...
1k views

### Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication. It is known that the determinant of an $n\times n$ matrix can ...
832 views

### 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 ...
427 views

### Lower bounds for linear satisfiability problem

In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
1k views

378 views

### Uniformity vs. nonuniformity in algebraic complexity theory

I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
517 views

### Riemann Hypothesis and Complexity Theory

It is known that "Assuming the generalized Riemann hypothesis (GRH) if VP = VNP then PH collapses to second level". Why would one think of a relation between VP,VNP and the Riemann hypothesis. Where ...
224 views

### Sorting using ring operations

Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time. Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done ...
331 views

151 views

### Recognition of a primitive root

Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz) Problem 18 of this list of open problems is about ...
491 views

### Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis. A very general question: Most algorithms compromise of ...
368 views

### Degree restriction for polynomials in $\mathsf{VP}$

why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
571 views