Popular Question - Badge - Theoretical Computer Science Stack Exchange

Popular Question

Question with 1,000 views. This badge can be awarded multiple times.

Awarded 2076 times.

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

Awarded yesterday

Luz

4272 silver badges10 bronze badges

Finding the smallest DFA that separates two words without using brute force search?

Awarded 2 days ago

Michael Wehar

5,1271 gold badge23 silver badges53 bronze badges

How to prove that USTCONN requires logarithmic space?

Awarded Nov 26 at 9:58

András Salamon

18.9k3 gold badges64 silver badges147 bronze badges

Consequences of $BQP \subseteq P/poly$?

Awarded Nov 23 at 22:36

Martin Schwarz

5,44625 silver badges41 bronze badges

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

Awarded Nov 22 at 12:32

Junqiang Peng

1637 bronze badges

Relationship between symmetry and computational intractability?

Awarded Nov 20 at 9:16

Mohammad Al-Turkistany

20.8k5 gold badges62 silver badges147 bronze badges

Are theoretical computer science conferences losing touch with reality?

Awarded Nov 20 at 1:25

DisgruntledTCSResearcher

3013 bronze badges

Algorithm to determine function equality on the simply typed lambda calculus?

Awarded Nov 19 at 3:18

MaiaVictor

3,11711 silver badges32 bronze badges

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

Awarded Nov 16 at 19:17

Michael Wehar

5,1271 gold badge23 silver badges53 bronze badges

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

Awarded Nov 15 at 19:56

Stattrav

5232 silver badges8 bronze badges

Qubits and permutation symmetry

Awarded Nov 9 at 2:09

kludg

1516 bronze badges

Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1

Awarded Nov 6 at 16:04

Robin Kothari

13.5k2 gold badges60 silver badges116 bronze badges

For which families of graphs is Generalized Geography in $P$?

Awarded Nov 6 at 5:47

R B

9,4385 gold badges33 silver badges74 bronze badges

Stephen Hawking's impact on computer science

Awarded Nov 4 at 8:26

Shaull

5,5311 gold badge21 silver badges32 bronze badges

Security of message authentication codes and tag size

Awarded Nov 2 at 10:31

Conrado

1234 bronze badges

Is the 3-sphere recognition problem NP-complete?

Awarded Nov 2 at 3:27

Joseph O'Rourke

3,74323 silver badges41 bronze badges

Does diagonalization captures the essence of class separation ?

Awarded Nov 1 at 19:11

Ludovic Patey

1,74311 silver badges22 bronze badges

Minimum Unsatisfiable Core

Awarded Oct 28 at 2:41

ryan

1356 bronze badges

Is there a list of forbidden subgraphs for comparability graphs?

Awarded Oct 26 at 9:25

Peng Zhang

1,4439 silver badges19 bronze badges

Can Elementary Affine Logic be used as the core type system of a practical programming language?

Awarded Oct 24 at 23:28

MaiaVictor

3,11711 silver badges32 bronze badges

Ownership types and Separation Logic

Awarded Oct 24 at 22:35

Uday Reddy

4,79628 silver badges39 bronze badges

Can you see that the Linz Halting Problem proof contains a fatal flaw?

Awarded Oct 24 at 17:18

polcott

451 silver badge9 bronze badges

Optimal sort algorithm in number of swaps

Awarded Oct 24 at 8:46

Jesse Zixi Zhang

1234 bronze badges

SDP relaxation of independent set

Awarded Oct 20 at 0:35

Yaroslav Bulatov

4,6811 gold badge25 silver badges39 bronze badges

C# Generics Research Papers

Awarded Oct 19 at 3:25

Kariem Ali

1436 bronze badges

What is the hardest instance for the group isomorphism problem?

Awarded Oct 18 at 7:50

adc

1771 silver badge14 bronze badges

Pre order traversal of an array [closed]

Awarded Oct 10 at 10:33

David Carpenter

1093 bronze badges

Number of Hamiltonian cycles on random graphs

Awarded Sep 28 at 10:11

Elely

3091 silver badge4 bronze badges

Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?

Awarded Sep 27 at 7:12

Zazaeil

2121 silver badge6 bronze badges

Is it still open to determine the complexity of computing the treewidth of planar graphs?

Awarded Sep 26 at 6:50

a3nm

8,89627 silver badges85 bronze badges

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

Awarded Sep 24 at 9:13

Karl Millson

734 bronze badges

Recent advances in computer science since 2010?

Awarded Sep 24 at 0:20

user12344567

6511 gold badge5 silver badges10 bronze badges

Finite state transducer that sorts

Awarded Sep 16 at 22:27

Eric O. Lebigot

1537 bronze badges

Circuit lower bounds and kolmogorov complexity

Awarded Sep 10 at 19:56

Magnus Find

8455 silver badges14 bronze badges

What should I do to switch from math department to cs to research tcs topics?

Awarded Sep 3 at 22:48

Charlie

613 bronze badges

Correspondence between complexity classes and logic

Awarded Sep 2 at 19:56

ripper234

86310 silver badges15 bronze badges

finding "hubs" in a graph

Awarded Aug 21 at 4:56

vzn

11k2 gold badges30 silver badges64 bronze badges

Tight Lower bounds on Savitch's theorem

Awarded Aug 14 at 17:16

gabgoh

1,54812 silver badges22 bronze badges

Problems in NP with non-trivial certificate

Awarded Aug 13 at 3:36

Command Master

4641 silver badge9 bronze badges

What are examples of recent relatively simple 'toolbox algorithms'?

Awarded Aug 7 at 23:03

Per Alexandersson

4023 silver badges8 bronze badges

Choosing random permutations in "strict" polynomial time

Awarded Aug 3 at 19:34

Rahab

3513 gold badges4 silver badges10 bronze badges

Approximate counting problem capturing BQP

Awarded Jul 28 at 2:55

Manu

7,6293 gold badges37 silver badges42 bronze badges

Expressiveness of Büchi vs CTL(*)

Awarded Jul 24 at 9:22

DaveBall aka user750378

4995 silver badges17 bronze badges

Is MLTT effectively pCiC without Prop?

Awarded Jul 23 at 13:57

user

6153 silver badges10 bronze badges

Costs of performing approx. nearest neighbor search in a skip quadtree

Awarded Jul 21 at 5:19

0__

17310 bronze badges

Does this game terminate?

Awarded Jul 20 at 13:05

Manu

7,6293 gold badges37 silver badges42 bronze badges

Efficiently modeling Turing machines in Peano Arithmetic

Awarded Jul 18 at 9:56

Marzio De Biasi

22.6k2 gold badges57 silver badges126 bronze badges

Properties expressible in 2-CNF or 2-SAT

Awarded Jul 14 at 17:26

Sameer Gupta

1717 bronze badges

Complexity of counting the number of edge covers of a graph

Awarded Jul 11 at 20:34

a3nm

8,89627 silver badges85 bronze badges

Biased binary search?

Awarded Jul 9 at 5:18

Display Name

3371 silver badge5 bronze badges

Formulating P vs NP without Turing machines

Awarded Jul 5 at 9:55

Dominic van der Zypen

8596 silver badges16 bronze badges

Original proof that "almost all decision problems are uncomputable"?

Awarded Jul 4 at 20:11

InfinitelyInquisitive

797 bronze badges

In the age of powerful AI, can all software be written using only tests?

Awarded Jul 4 at 11:51

Maciej Bledkowski

1615 bronze badges

Is there a Quantum equivalent of the Time hierarchy theorem ?

Awarded Jun 29 at 8:16

Zelah 02

1,5787 silver badges16 bronze badges

How can an inherited attribute be simulated using a synthesized attribute?

Awarded Jun 28 at 12:06

saikat

1755 bronze badges

A generalization of edge cover

Awarded Jun 25 at 19:16

defg

413 bronze badges

Generating a random connected bipartite graph

Awarded Jun 20 at 19:55

cglacet

1414 bronze badges

Solo single author paper vs the comfort of having you advisor on the paper?

Awarded Jun 19 at 21:40

user3508551

1,0785 silver badges12 bronze badges

Maximum shortest word accepted by pushdown automata

Awarded Jun 15 at 17:48

Antimony

9175 silver badges15 bronze badges

Array slice reversing data-structure

Awarded Jun 15 at 9:35

Aryabhata

1,8553 gold badges21 silver badges29 bronze badges

2 3 4 5

…

35 Next