Network profile

galah92

Reputation

297

297

Apr
Jul
Oct
Jan

Top tag

space-complexity

Next privilege

300 Rep.

Create new tags

Badges

1

8

Newest

Popular Question

Next badge

0/1

Impact

0 posts edited

0 helpful flags

12 votes cast

12 Questions

Votes Activity Newest Views

1

4

votes

1

answer

216

views

Non-existence of PSPACE-hard unary language

complexity-theory space-complexity

Apr 4 '19 at 11:02 David Richerby 78.5k

2

4

votes

1

answer

172

views

Between every two MST's there's a series of “nearby” MST's

graphs minimum-spanning-tree

Feb 15 '18 at 21:35 Willard Zhan 1,163

1

2

votes

1

answer

262

views

Vertex Cover of size at most $\log n$

complexity-theory vertex-cover

Jun 8 '19 at 10:07 Oren Milman 113

2

votes

1

answer

84

views

Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

formal-languages context-free formal-grammars

Feb 9 '18 at 11:12 Raphael♦ 69.1k

1

vote

1

answer

28

views

$NL^2 = NDSPACE(\log^2n)$ is closed under complement

complexity-theory space-complexity

Jun 20 '19 at 13:13 Yuval Filmus 242k

1

vote

1

answer

56

views

Derandomize MAX-CUT problem using $\log n$ bits

randomness max-cut

Jun 18 '19 at 11:44 Yuval Filmus 242k

1

vote

1

answer

56

views

Prove $EXP \subset E^E$

complexity-theory time-complexity

Aug 1 '18 at 13:11 Yuval Filmus 242k

1

vote

2

answers

61

views

STCON in L using matrix multipication algorithm?

space-complexity

Jul 12 '18 at 13:13 David Richerby 78.5k

1

vote

0

answers

609

views

Constructing a turing machine from a PDA - dealing with non-determinism

turing-machines pushdown-automata simulation

Dec 19 '17 at 10:23 Raphael♦ 69.1k

1

vote

1

answer

1k

views

How to find the equivalence classes of a regular language

regular-languages

Nov 25 '17 at 14:45 Yuval Filmus 242k

0

votes

1

answer

110

views

Space complexity for connectivity problem with given graph diameter

graphs space-complexity

Mar 22 '18 at 11:11 quicksort 4,042

-1

votes

1

answer

567

views

Binary search trees: multiple `Successor()` calls

time-complexity binary-search-trees

May 14 '17 at 17:09 Yuval Filmus 242k

Computer Science Stack Exchange works best with JavaScript enabled