user avatar
user avatar
user avatar
ivmihajlin
  • Member for 7 years, 10 months
  • Last seen more than 3 years ago
8 votes
0 answers
110 views

Reference for a circuit lower bound for slightly superexponential time

7 votes
1 answer
239 views

Non-uniform lower bounds from uniform

7 votes
2 answers
1k views

Partition planar graph into connected subgraphs of equal size

7 votes
1 answer
151 views

Lower bounds for noncommutative arithmetic circuits with exact division?

6 votes
2 answers
305 views

How to find a non-zero point of a non-zero polynomial of low degree?

5 votes
1 answer
135 views

Reference request: complexity of $k$-partite $k$-SAT

5 votes
0 answers
145 views

Online triangle counting

4 votes
1 answer
164 views

Algorithms in preprocessed universe [closed]

4 votes
1 answer
183 views

Hardness of Subgraph isomorphism problem for sparse pattern graph

4 votes
1 answer
152 views

$NotTooManyP^{cc}$ class in communication complexity

4 votes
0 answers
170 views

Nondeterministic communication complexity of Hamming distance

3 votes
0 answers
165 views

Circuit's with gate computing only "simple" functions

3 votes
0 answers
180 views

What does it take to be accepted to FUN?

2 votes
1 answer
108 views

Low-depth arithmetic complexity of the product of $k$ matrices

2 votes
0 answers
51 views

Arithmetic circuits with restrictions on occurrence of pairs of variables

1 vote
0 answers
49 views

What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]