Stack Exchange

Stasys

Frankfurt am Main, Germany

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

top accounts reputation activity bookmarks subscriptions
Top Questions
49 votes

Monotone complexity of s-t connectivity

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

33 votes

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

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

32 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, 2012 at 15:49
cstheory.stackexchange.com

25 votes

Why is HAMILTONIAN CYCLE so different from PERMANENT?

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits asked Nov 18, 2014 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, 2014 at 16:58
cstheory.stackexchange.com

21 votes

Clique problem on fixed graphs

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

20 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, 2017 at 16:50
cstheory.stackexchange.com

17 votes

Can short-distance connectivity be harder than connectivity?

cc.complexity-theory graph-algorithms circuit-complexity lower-bounds dynamic-programming asked Apr 3, 2015 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, 2017 at 17:40
cstheory.stackexchange.com

15 votes

Any polynomial which is hard to count but easy to decide?

circuit-complexity lower-bounds arithmetic-circuits cc-complexity-theory asked Oct 24, 2014 at 16:17
cstheory.stackexchange.com

1 2

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

25
Monotone arithmetic circuits
cstheory.stackexchange.com

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

20
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
How expensive may it be to destroy all long s-t paths in a DAG?
cstheory.stackexchange.com

8
OR-circuit complexity of a dense linear operator
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

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

5
Communication complexity with a referee
cstheory.stackexchange.com