Kristoffer Arnsfelt Hansen's user avatar
Kristoffer Arnsfelt Hansen's user avatar
Kristoffer Arnsfelt Hansen's user avatar
Kristoffer Arnsfelt Hansen
  • Member for 13 years, 7 months
  • Last seen more than a week ago
22 votes
Accepted

Can we count in depth $\frac{\lg n}{\lg \lg n}$?

22 votes
Accepted

How much time to recognize palindromes in logarithmic space?

21 votes

Guidelines to reduce general TSP to Triangle TSP

20 votes
Accepted

Is qsort linear when sorting only two values?

18 votes
Accepted

Better lower bounds than 3n for non-boolean functions?

17 votes
Accepted

A fixed-depth characterization of $TC^0$? $NC^1$?

16 votes

Relationship between SPACE(n) and E

15 votes
Accepted

Does the $\mathsf{TC^0}$ hierarchy collapse?

14 votes
Accepted

Does L have a definition in terms of circuits?

13 votes

What is the complexity class most closely associated with what the human mind can accomplish quickly?

13 votes
Accepted

Hamiltonian cycle on graphs without small cycles

12 votes

Parity and $AC^0$

11 votes

Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?

11 votes

Circuit complexity of Majority function

10 votes

Equivalence of feasibility checking and optimization for linear systems

8 votes
Accepted

What is $DTIME(n^a)^{DTIME(n^b)}$?

8 votes

Parallel algorithms for directed st-connectivity

7 votes
Accepted

Simple reduction to unbounded knapsack?

7 votes
Accepted

Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure?

7 votes

"Steve's class": origin of SC

7 votes

Constant Depth Circuit Computing Threshold Function

7 votes
Accepted

Topological sort with constraints on the relative difference between the vertex labels

6 votes
Accepted

Solving Linear Equations over $Z_q$

6 votes
Accepted

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph

6 votes
Accepted

Gap in degree of representations of candidate boolean functions

6 votes
Accepted

Complexity of reversible Circuit Value

6 votes

Simple question about pseudorandom generator

6 votes
Accepted

Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

5 votes

Heuristics for graph bisection

5 votes

Decidability of transcendental numbers