User Soham Chatterjee

5 votes

1 answer

135 views

DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

asked Dec 11, 2022 at 16:25

4 votes

0 answers

79 views

How to learn the intuition behind probabilistic arguments in Algebraic Complexity lower bounds

asked Nov 2, 2022 at 21:14

3 votes

0 answers

113 views

Reference Request: Circuit Complexity Theory Course

asked Apr 9, 2023 at 2:18

1 vote

0 answers

90 views

$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]

asked Apr 21, 2023 at 11:50

1 vote

0 answers

63 views

Pfaffian orientation algorithm for planar graphs

asked Oct 1, 2023 at 15:33

1 vote

1 answer

69 views

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

asked Oct 26, 2023 at 19:07

0 votes

0 answers

20 views

What is a tight set for a face $F$ of the perfect matching polytope

asked Jun 9 at 20:23

0 votes

1 answer

82 views

In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

asked Nov 7, 2022 at 22:46

0 votes

0 answers

68 views

Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$

asked Nov 1, 2022 at 15:31

Stack Exchange Network

9 Questions

DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

How to learn the intuition behind probabilistic arguments in Algebraic Complexity lower bounds

Reference Request: Circuit Complexity Theory Course

$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]

Pfaffian orientation algorithm for planar graphs

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

What is a tight set for a face $F$ of the perfect matching polytope

In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$