Nice Question Badge - Theoretical Computer Science Stack Exchange

jun 16 at 20:43

Can you identify the sum of two permutations in polynomial time? — Peter Shor 12.8k14679

jun 14 at 21:29

Counting grid colorings that avoid certain features — mikero 1,540719

jun 12 at 11:16

Does the $\mathsf{TC^0}$ hierarchy collapse? — Kaveh♦ 9,628232113

jun 11 at 21:16

What is the minimum required depth of reductions for NP-hardness of SAT? — Kaveh♦ 9,628232113

jun 11 at 21:06

Does a noisy version of Conway's game of life support universal computation? — Gil Kalai 2,3761337

jun 9 at 14:55

Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$) — Giorgio Camerani 2,387839

jun 8 at 21:12

Is there a book/survey-paper outlining language class hierarchies, closure properties, etc — jmite 1107

jun 6 at 18:54

Edge-partitioning cubic graphs into claws and paths — Anthony Labarre 1,8991924

may 31 at 15:37

Improved lower bound on monotone circuit complexity of perfect matching? — slimton 860517

may 31 at 11:11

the largest element of a matrix product — MaxB 512

may 26 at 21:40

Resources for mathematicians hoping to learn more computer science — Clive Newstead 1534

may 23 at 20:00

Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size — Arul 989215

may 23 at 19:15

Is Bayesian updating computationally unfeasible? — Timmy 1214

may 23 at 4:54

Checking if all products of a set of matrices eventually equal zero — robinson 36518

may 21 at 17:57

What is the complexity of this edge coloring problem? — RIC_Eien 1113

may 21 at 2:11

When does (or should) Theoretical CS care about intuitionistic proofs? — usul 1,059210

may 20 at 4:08

Is Quasi-polynomial time in PSPACE? — Tayfun Pay 597426

may 16 at 20:28

What is the number of languages accepted by a DFA of size $n$? — Janoma 731323

may 16 at 19:38

Data structure for updates on intervals and querying number of zeros — Christoph Dürr 512

may 14 at 0:21

Wikipedia-style explanation of Geometric Complexity Theory — Alessandro Cosentino 1,9001425

may 11 at 20:33

Best known deterministic time complexity lower bound for a natural problem in NP — Anonymous 930314

may 11 at 16:37

Do people look at loop nestness in boolean circuits? — Radu GRIGore 2,4991136

may 11 at 13:21

Finding short and fat paths — dan_x 336111

may 10 at 13:14

Is “Is a permutation p an automorphism of a graph in my set?” NP-complete? — Douglas S. Stones 36319

may 10 at 4:36

Fano's inequality in the high error regime — Or Meir 1,718415

may 9 at 1:19

Why economists should care about computational complexity — Artem Kaznatcheev 4,75711370

may 6 at 14:49

Complexity of the densest k-subgraph problem on planar graphs — Aaron Schild 838

may 3 at 6:03

Implications of approximating the determinant — Lior Eldar 334111

may 2 at 22:45

Testing for positivity instead of equality — Suresh Venkat♦ 19.6k252191

may 1 at 11:03

Complexity to compute the eigenvalue signs of the adjacency matrix — Dimitris 556111

apr 30 at 22:29

The complexity of sampling (approximately) the Fourier transform of a Boolean function — Gil Kalai 2,3761337

apr 30 at 3:09

Counting words accepted by a regular grammar — Charles 719313

apr 29 at 9:08

Count the number of spanning trees fast — Sergey Finsky 1808

apr 25 at 16:25

Reference for NP-hardness of 3-colouring? — Thore Husfeldt 27529

apr 20 at 8:23

How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$? — a guest 8314

apr 19 at 15:51

How can I use my computational theory and analysis powers for the greater good? — PhD 733349

apr 16 at 13:29

Small graph with gap between chromatic and vector chromatic number? — Thore Husfeldt 27529

apr 14 at 15:19

A 3-CNF formula that requires resolution width $5$ — Jan Johannsen 1,392516

apr 14 at 15:19

Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$ — Tayfun Pay 597426

apr 11 at 3:40

Witnesses for mathematical software — Anush 564

apr 10 at 0:27

Recovering a parse forest from an Earley parser? — templatetypedef 302110

apr 5 at 20:41

Constructively efficient algorithms without efficient correctness and efficiency proof — Kaveh♦ 9,628232113

apr 5 at 13:41

Edit distance with move operations — Jukka Suomela 6,84422885

apr 5 at 1:10

Is there a list of canonical problems in distributed systems? — marcmagransdeabril 715

apr 4 at 21:03

Explaining Applicative functor in categorical terms - monoidal functors — Petr Pudlák 67710

apr 4 at 6:44

Enumerating all pairs of disjoint paths — Amateur 512

apr 4 at 1:48

Matrix rigidity and uses of matrices with low rigidity — Arul 989215

apr 3 at 18:08

How much independence is required for separate chaining? — jbapple 2,31621229

apr 2 at 19:38

Runtime of Grover's algorithm — Dan Stahlke 1694

apr 1 at 11:41

How can a problem be in NP, be NP-hard and not NP-complete? — Austin Buchanan 4559

mar 31 at 13:05

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$? — domotorp 3,418831

mar 30 at 13:19

Does there exist an extension of regular expressions that captures the context free languages? — Alex ten Brink 1,942729

mar 29 at 19:39

Subset sum vs. Subset product (strong vs. weak NP hardness) — RDN 706

mar 28 at 17:50

Bigger picture behind the choice of matrices in the Strassen algorithm — user17762 1617

mar 28 at 2:49

funsplit and polarity of Pi-types — pedagand 1235

mar 27 at 16:08

Bootstrapping a Finger Tree Structure — jbondeson 1986

mar 26 at 18:47

Automated theorem proving in linear logic — Anonymous 930314

mar 25 at 15:21

What is the logarithm or root operation in type-space? — efrey 9316

mar 25 at 13:41

Is induced subgraph isomorphism easy on an infinite subclass? — sdcvvc 490210

mar 25 at 10:10

Is Parity-P contained in PP? — Timothy Chow 4,0831730

Help Center > Badges

This badge has been awarded 1361 times. Recently awarded to: