Network profile

galah92

Reputation

297

297
270
243

Aug
Nov
Feb
May

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

13 Questions

Votes Activity Newest Views

1

4

votes

1

answer

205

views

Non-existence of PSPACE-hard unary language

complexity-theory space-complexity

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

2

4

votes

1

answer

163

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

209

views

Vertex Cover of size at most $\log n$

complexity-theory vertex-cover

Jun 8 '19 at 10:07 Oren Milman 103

2

votes

1

answer

82

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♦ 67.6k

1

vote

1

answer

27

views

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

complexity-theory space-complexity

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

1

vote

1

answer

39

views

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

randomness max-cut

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

1

vote

1

answer

52

views

Prove $EXP \subset E^E$

complexity-theory time-complexity

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

1

vote

2

answers

53

views

STCON in L using matrix multipication algorithm?

space-complexity

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

1

vote

0

answers

541

views

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

turing-machines pushdown-automata simulation

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

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 225k

0

votes

0

answers

45

views

Dominating Set Gap Problem Reduction

reductions vertex-cover

Jun 7 '19 at 5:30 galah92 297

0

votes

1

answer

102

views

Space complexity for connectivity problem with given graph diameter

graphs space-complexity

Mar 22 '18 at 11:11 quicksort 3,982

-1

votes

1

answer

532

views

Binary search trees: multiple `Successor()` calls

time-complexity binary-search-trees

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

Computer Science Stack Exchange works best with JavaScript enabled