## Would $\Sigma_i^P \neq \Pi_i^P$ imply that polynomial hierachy cannot collapse to the $i$-th level?

If $$\Sigma_i^P = \Pi_i^P$$, then it follows that the polynomial hierarchy collapses to the $$i$$-th level.

What about the case $$\Sigma_i^P \neq \Pi_i^P$$? For example, consider the case of $$NP \neq coNP$$. As far as I understand, this would imply the polynomial hierarchy cannot collapse to the first level, since if $$PH =NP$$, then in particular, $$coNP \subseteq NP$$, which means $$NP = coNP$$. Can we expand this idea to proof the general case: $$\Sigma_i^P \neq \Pi_i^P$$ implies $$PH$$ cannot collapse to $$i$$-th level?

Posted on Categories proxies

## Boolean circuit size of $i$th bit of determinant?

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers.

Is there a polynomial size boolean circuit for $$i$$th bit of determinant and is it still logarithmic depth?

Posted on Categories proxies

## Lowering $i$th shortest vector of a lattice

LLL guarantees that we can find a basis $$v_1,\dots,v_n$$ of a lattice in $$\mathbb R^n$$ with

$$\|v_i\|\leq \gamma_{i,n} det(\Lambda)^{1/(n-i+1)}$$ where $$\gamma_i$$ is a function only of $$i$$ and $$n$$.

1. Are there lattices where this cannot be improved to $$\|v_i\|\leq \gamma_{i,n} det(\Lambda)^{1/(n-i+2)}$$?

2. In general are there algorithms (possibly in exponential time) which can guarantee $$\|v_i\|\leq \gamma_{i,n} det(\Lambda)^{1/(n-i+2)}$$?