Tour
About Us
Meta
Loading…
current community
Stack Exchange
chat
Meta Stack Exchange
your communities
Sign up
or
log in
to customize your list.
more stack exchange communities
company blog
Log in
Stack Exchange
All Sites
Top Users
Digests
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
next
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
Stack Exchange works best with JavaScript enabled