Network profile

C.P.

Reputation

972

982
587
193

2018
2019
2020
2021

Top tag

automata-theory

Next privilege

1,000 Rep.

See votes

Badges

5

12

Newest

Yearling

Next badge

0/1

Impact

1 post edited

0 helpful flags

83 votes cast

8 Bookmarks

Votes Activity Newest Views Added

23

votes

2

answers

527

views

Testing whether letters can be scheduled to achieve a word in a regular language

cc.complexity-theory np-hardness automata-theory regular-language scheduling

Mar 4 '18 at 21:29 a3nm 6,926

17

votes

0

answers

469

views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

cc.complexity-theory complexity-classes circuit-complexity advice-and-nonuniformity logspace

Oct 22 '14 at 10:11 Damiano Mazza 4,318

11

votes

0

answers

339

views

A dynamic data structure to list triangles

graph-theory ds.data-structures

Jul 6 '19 at 14:52 boinkboink 173

9

votes

0

answers

106

views

Expected value of the evaluation of Boolean circuits of depth $2n$

reference-request circuit-complexity circuits

Jul 17 '18 at 16:21 J.-E. Pin 4,454

9

votes

0

answers

102

views

Graphs with minimal-size induced subgraphs

reference-request graph-theory extremal-combinatorics

Aug 9 '18 at 8:55 Christian Komusiewicz 1,657

6

votes

1

answer

166

views

Arranging letters to make a word in a regular language

cc.complexity-theory ds.algorithms fl.formal-languages regular-language

Oct 21 '19 at 18:57 a3nm 6,926

6

votes

2

answers

317

views

On the complexity of a “list” datastructure in the RAM model

ds.algorithms complexity machine-models

May 25 at 7:28 David Eppstein 49.3k

3

votes

0

answers

49

views

AMQ (Bloom-filter like structure) lower bounds

optimization memory

Jun 10 '19 at 18:52 haael 125

Theoretical Computer Science Stack Exchange works best with JavaScript enabled