Stack Exchange

Stasys

Frankfurt am Main, Germany

http://www.thi.informatik.uni-frankfurt.de/~jukna/

top accounts reputation activity favorites subscriptions
Top Questions
45 votes

Monotone complexity of s-t connectivity

cc.complexity-theory circuit-complexity lower-bounds dynamic-programming monotone asked Oct 6 '12 at 12:45
cstheory.stackexchange.com

30 votes

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

graph-theory lower-bounds directed-acyclic-graph dynamic-programming shortest-path asked Dec 3 '12 at 15:49
cstheory.stackexchange.com

29 votes

Is BPP= P known for ANY uniform model of computation?

cc.complexity-theory circuit-complexity derandomization asked Nov 17 '17 at 21:14
cstheory.stackexchange.com

23 votes

Why is HAMILTONIAN CYCLE so different from PERMANENT?

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits asked Nov 18 '14 at 18:02
cstheory.stackexchange.com

21 votes

Arithmetic circuits with just one threshold gate

circuit-complexity arithmetic-circuits cc-complexity-theory asked Nov 2 '14 at 16:58
cstheory.stackexchange.com

21 votes

Clique problem on fixed graphs

cc.complexity-theory optimization circuit-complexity asked Apr 2 '12 at 19:13
cstheory.stackexchange.com

16 votes

Can short-distance connectivity be harder than connectivity?

cc.complexity-theory graph-algorithms circuit-complexity lower-bounds dynamic-programming asked Apr 3 '15 at 17:00
cstheory.stackexchange.com

16 votes

VC dimension of polynomials over tropical semirings?

co.combinatorics circuit-complexity algebraic-complexity arithmetic-circuits vc-dimension asked Mar 15 '17 at 17:40
cstheory.stackexchange.com

16 votes

Is BPP vs. P a real problem after we know BPP lies in P/poly?

cc.complexity-theory circuit-complexity machine-learning derandomization asked Oct 6 '17 at 16:50
cstheory.stackexchange.com

15 votes

Is Dynamic Programming never weaker than Greedy?

cc.complexity-theory circuit-complexity lower-bounds dynamic-programming asked Dec 21 '15 at 22:30
cstheory.stackexchange.com

1 2

Top Answers
25
Monotone arithmetic circuits
cstheory.stackexchange.com

25
Is there a better than linear lower bound for factoring and discrete log?
cstheory.stackexchange.com

24
Kolmogorov's conjecture that $P$ has linear-size circuits
cstheory.stackexchange.com

18
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
cstheory.stackexchange.com

15
Formula size lower bounds for AC0 functions
cstheory.stackexchange.com

14
Status on circuit lower bounds for polylog-bounded depth circuits
cstheory.stackexchange.com

13
Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results
cstheory.stackexchange.com

12
Formula size lower bounds for AC0 functions
cstheory.stackexchange.com

11
Circuit lower bounds over arbitrary sets of gates
cstheory.stackexchange.com

11
Is $AC^0/poly \cap NP$ contained in $P$?
cstheory.stackexchange.com

11
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
cstheory.stackexchange.com

9
VC dimension of polynomials over tropical semirings?
cstheory.stackexchange.com

8
Razborov's Approximation methods
cstheory.stackexchange.com

8
OR-circuit complexity of a dense linear operator
cstheory.stackexchange.com

8
How expensive may it be to destroy all long s-t paths in a DAG?
cstheory.stackexchange.com

7
P/poly vs NP separation based on circuit trees instead of DAGs
cstheory.stackexchange.com

6
Lower bounds on monotone space complexity
cstheory.stackexchange.com

6
Is Dynamic Programming never weaker than Greedy?
cstheory.stackexchange.com

5
Upper bounds on the circut depth
cstheory.stackexchange.com

5
Communication complexity with a referee
cstheory.stackexchange.com