Nice Question Badge - Theoretical Computer Science Stack Exchange

1d ago

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

1d ago

Is Bayesian updating computationally unfeasible? — Timmy 1214

2d ago

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

may 21 at 17:57

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

may 21 at 2:11

When does (or should) Theoretical CS care about intuitionistic proofs? — usul 994210

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 731223

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,8951425

may 11 at 20:33

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

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,698415

may 9 at 1:19

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

may 6 at 14:49

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

may 3 at 6:03

Implications of approximating the determinant — Lior Eldar 327110

may 2 at 22:45

Testing for positivity instead of equality — Suresh Venkat♦ 19.5k252190

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,2761336

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 22529

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 22529

apr 14 at 15:19

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

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 292110

apr 5 at 20:41

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

apr 5 at 13:41

Edit distance with move operations — Jukka Suomela 6,83422884

apr 5 at 1:10

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

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 971215

apr 3 at 18:08

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

apr 2 at 19:38

Runtime of Grover's algorithm — Dan Stahlke 1594

apr 1 at 11:41

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

mar 31 at 13:05

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

mar 30 at 13:19

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

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 890213

mar 25 at 15:21

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

mar 25 at 13:41

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

mar 25 at 10:10

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

mar 22 at 23:42

Smooth Complexity of the Nonnegative Permanent — Zelah 02 739211

mar 22 at 14:07

Linear time in-place riffle shuffle algorithm — Johny 534

mar 21 at 12:20

Understanding the talks in Conferences and Workshops — Gold 1246

mar 20 at 17:42

What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes? — Tayfun Pay 597426

mar 20 at 17:42

What do we know about the phase transition of #P-Complete problems? — Tayfun Pay 597426

mar 19 at 2:39

Sorting using a black box — AmeerJ 2058

mar 17 at 21:53

A game of positioning overlapping circles to maximize travel time between them — Josh 1789

mar 16 at 18:57

Can Scheme's call/cc implement all known control flow structures? — csl 588

mar 16 at 13:12

Are there any algorithms for SAT solving which are not DPLL based? — Anonymous 890213

mar 16 at 13:12

Can addition be carried out in less than depth 5? — Anonymous 890213

mar 16 at 13:12

When can we say that two programs are different? — Anonymous 890213

Badge

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