Alexey Milovanov's user avatar
Alexey Milovanov's user avatar
Alexey Milovanov's user avatar
Alexey Milovanov
  • Member for 9 years, 7 months
  • Last seen more than a month ago
13 votes
3 answers
1k views

A game on several graphs

11 votes
0 answers
342 views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

11 votes
1 answer
474 views

Is DSPACE(n) = DSPACE(1.5n)?

10 votes
0 answers
224 views

On Courcelle's question about Monadic second-order logic with cardinality predicates

10 votes
1 answer
402 views

Is this game EXPSPACE-complete?

10 votes
1 answer
501 views

What is the complexity of this game?

10 votes
0 answers
150 views

Fine-grained complexity for game-type problems

9 votes
1 answer
378 views

Noether’s Normalization Lemma for finite fields

9 votes
1 answer
495 views

On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

7 votes
1 answer
699 views

Difference between time-bounded and memory-bounded Kolmogorov complexity

7 votes
0 answers
124 views

What can we say about AM[log n]?

7 votes
1 answer
163 views

Finding a certificate if E=NE

6 votes
1 answer
390 views

DTIME and PSPACE

6 votes
1 answer
439 views

Parity P and AM

6 votes
1 answer
258 views

Finding a minimal addition chain for a given number

6 votes
0 answers
141 views

Computing Sequences with Addition Chains In pseudopolynomial time?

5 votes
1 answer
212 views

What circuit depth is enough to compute a log-space complete problem?

5 votes
0 answers
77 views

Finding of dimension of algebraic varieties

4 votes
0 answers
155 views

More powerful generator than Nisan-Wigderson one

4 votes
3 answers
431 views

Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

4 votes
1 answer
261 views

Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

4 votes
1 answer
199 views

A question about decision tree complexity

4 votes
1 answer
277 views

On complexity class $\mathsf{\Pi_2 L}$

4 votes
0 answers
108 views

$\mathsf{NL}$ vs. $\mathsf{AC}^1$

3 votes
0 answers
65 views

What is $\mathrm{NC}^0$-uniform reduction

3 votes
1 answer
180 views

Theorem of Sudan, Trevisan and Vadhan about list-decoding

3 votes
2 answers
300 views

Classes between PH and PSPACE

2 votes
0 answers
72 views

How to improve this pseudorandom generator?

2 votes
1 answer
103 views

Complexity of computation of ANF-form (Zhegalkin polynomial)

2 votes
0 answers
211 views

Derandomization of Polynomial Identity Testing