Enlightened - Badge - Theoretical Computer Science Stack Exchange

Enlightened

First to answer and accepted with score of 10 or more. This badge can be awarded multiple times.

Awarded 1330 times.

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

Awarded Nov 21 at 17:20

Huck Bennett

4,7882 gold badges33 silver badges46 bronze badges

What exactly is "large elimination"?

Awarded Nov 19 at 7:05

cody

13.7k1 gold badge47 silver badges99 bronze badges

Chomsky Schützenberger enumeration theorem

Awarded Oct 28 at 10:02

Jeffrey Shallit

6,96732 silver badges38 bronze badges

Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth

Awarded Oct 9 at 16:25

David Eppstein

50.9k3 gold badges169 silver badges278 bronze badges

Time complexity of d-dimensional convex hull

Awarded Oct 8 at 14:55

David Eppstein

50.9k3 gold badges169 silver badges278 bronze badges

Complexity of sorting

Awarded Sep 28 at 18:02

Yuval Filmus

14.3k1 gold badge48 silver badges92 bronze badges

Law of the Excluded Middle in complexity theory

Awarded Sep 21 at 22:57

Ryan Williams

27.3k7 gold badges114 silver badges163 bronze badges

Flood fill vs depth first search

Awarded Sep 13 at 19:45

J..y B..y

2,7331 gold badge22 silver badges34 bronze badges

Is bounded-error probabilistic computation sensitive to transition types?

Awarded Sep 1 at 10:48

Peter Shor

24.3k4 gold badges92 silver badges131 bronze badges

Structural Complexity Theory References

Awarded Aug 24 at 12:11

Joshua Grochow

36.9k4 gold badges129 silver badges227 bronze badges

Dependent types over Church-encoded type in PTS/CoC

Awarded Aug 9 at 16:04

Gabriella Gonzalez

2162 silver badges4 bronze badges

Stronger "induction" principles than induction-recursion

Awarded Aug 5 at 7:40

Dan Doel

9218 silver badges8 bronze badges

Quickly finding empty-string producing nonterminals in a CFG

Awarded Jul 31 at 14:34

Warren Schudy

1,87416 silver badges15 bronze badges

Is equivalence of unambiguous context-free languages decidable?

Awarded Jul 17 at 9:37

Lorenzo

1182 silver badges6 bronze badges

Formulating P vs NP without Turing machines

Awarded Jul 5 at 8:42

Emil Jeřábek

16.9k3 gold badges60 silver badges89 bronze badges

Additive versus multiplicative accuracy

Awarded Jun 20 at 15:17

Neal Young

9,59531 silver badges57 bronze badges

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Awarded May 27 at 21:12

Andras Farago

11.3k37 silver badges70 bronze badges

Where is the model theory in programming language theory?

Awarded May 25 at 10:11

Damiano Mazza

5,2731 gold badge24 silver badges36 bronze badges

Computational Complexity of Computer Vision Problems

Awarded May 15 at 9:51

Lev Reyzin♦

11.9k13 gold badges63 silver badges102 bronze badges

What is the formal definitions of the reduction related to the "call/cc" (call with the current continuation) operator?

Awarded Apr 6 at 10:17

Martin Berger

11.4k3 gold badges39 silver badges71 bronze badges

Fault-tolerant programming languages / paradigms?

Awarded Mar 30 at 23:33

Martin Berger

11.4k3 gold badges39 silver badges71 bronze badges

Find odd-ranked numbers from a list

Awarded Mar 28 at 23:42

Neal Young

9,59531 silver badges57 bronze badges

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

Awarded Feb 24 at 12:09

Joshua Grochow

36.9k4 gold badges129 silver badges227 bronze badges

Strong normalization property of CoC inside CoC

Awarded Feb 7 at 12:06

cody

13.7k1 gold badge47 silver badges99 bronze badges

Is #P contained in PSPACE?

Awarded Jan 29 at 15:41

Daniel Apon

5,9611 gold badge37 silver badges53 bronze badges

Algebraic equivalent of SAT?

Awarded Jan 9 at 1:18

D.W.

11.7k2 gold badges34 silver badges77 bronze badges

Explaining monad transformers in categorical terms

Awarded Dec 29, 2022 at 13:32

Andrej Bauer

28.3k1 gold badge80 silver badges130 bronze badges

Did Jinliang Wang solve the P versus NP problem?

Awarded Dec 27, 2022 at 17:35

Charles

1,73712 silver badges23 bronze badges

Is $PSPACE$ believed to be different than $PP$?

Awarded Dec 15, 2022 at 14:37

Lieuwe Vinkhuijzen

1,95914 silver badges20 bronze badges

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

Awarded Dec 8, 2022 at 11:21

Noah Schweber

6485 silver badges11 bronze badges

How do separations in of query complexities imply complexity class separations relative to oracles?

Awarded Dec 8, 2022 at 11:21

Wei Zhan

7235 silver badges17 bronze badges

How to tell if an effect is algebraic?

Awarded Nov 14, 2022 at 13:09

Andrej Bauer

28.3k1 gold badge80 silver badges130 bronze badges

Unique $k$-SAT benchmarks

Awarded Nov 4, 2022 at 18:26

D.W.

11.7k2 gold badges34 silver badges77 bronze badges

Is Church-pentation implementable in Agda?

Awarded Nov 4, 2022 at 14:11

Dan Doel

9218 silver badges8 bronze badges

Number of permutations that satisfy a given set of comparisons

Awarded Oct 14, 2022 at 23:21

a3nm

8,89627 silver badges85 bronze badges

$k$-clique in $k$-partite graph

Awarded Oct 13, 2022 at 11:52

Thomas S

1,41711 silver badges14 bronze badges

Hartmanis-Stearns conjecture and the computable transcendental numbers

Awarded Sep 21, 2022 at 4:02

Yuval Filmus

14.3k1 gold badge48 silver badges92 bronze badges

Is the maximum independent set in cubic planar graphs NP-complete?

Awarded Aug 1, 2022 at 21:01

Gamow

5,7726 gold badges24 silver badges39 bronze badges

Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

Awarded Jun 9, 2022 at 15:40

Neel Krishnaswami

32.4k1 gold badge100 silver badges165 bronze badges

The complexity of the permanent of low rank matrices

Awarded Jun 8, 2022 at 15:05

smapers

8495 silver badges10 bronze badges

Are there survey papers in theoretical computer science?

Awarded May 28, 2022 at 9:01

Joshua Grochow

36.9k4 gold badges129 silver badges227 bronze badges

How to show that the median cannot be maintained in $O(1)$ time?

Awarded Apr 30, 2022 at 7:32

Louis

7756 silver badges9 bronze badges

"Spurious" Type Equivalences in MLSub/Algebraic Subtyping

Awarded Apr 28, 2022 at 4:32

Neel Krishnaswami

32.4k1 gold badge100 silver badges165 bronze badges

Generating Graphs with Trivial Automorphisms

Awarded Apr 22, 2022 at 23:18

Joshua Grochow

36.9k4 gold badges129 silver badges227 bronze badges

The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis

Awarded Apr 9, 2022 at 9:04

Andrej Bauer

28.3k1 gold badge80 silver badges130 bronze badges

Step-indexing: Where to begin?

Awarded Mar 24, 2022 at 8:33

cody

13.7k1 gold badge47 silver badges99 bronze badges

$AC^0$[subexp] vs. NC

Awarded Mar 23, 2022 at 11:26

Emil Jeřábek

16.9k3 gold badges60 silver badges89 bronze badges

Why does it matter how difficult a proof is?

Awarded Mar 4, 2022 at 18:05

anonymous_user_1234567

1441 silver badge2 bronze badges

Finding appropriate spanning tree of connected bipartite graph

Awarded Jan 21, 2022 at 17:41

Neal Young

9,59531 silver badges57 bronze badges

Find research partner (profession and beginner)

Awarded Jan 15, 2022 at 14:47

usul

7,5951 gold badge25 silver badges45 bronze badges

Swapping arguments of variables in higher-order pattern unification

Awarded Dec 30, 2021 at 14:51

András Kovács

1,4448 silver badges7 bronze badges

Universal and existential types

Awarded Dec 14, 2021 at 0:51

Andrej Bauer

28.3k1 gold badge80 silver badges130 bronze badges

Which universities in the U.S. are doing research in type theory?

Awarded Dec 2, 2021 at 18:06

Joey Eremondi

2,83015 silver badges29 bronze badges

The entropy of a convolution over the hypercube

Awarded Dec 1, 2021 at 13:35

Colin McQuillan

3,54622 silver badges29 bronze badges

Travelling Salesman and Planar Travel - Generalized TSP

Awarded Nov 30, 2021 at 23:36

Suresh Venkat

32k4 gold badges94 silver badges271 bronze badges

Full names of C. K. Chow and C. N. Liu

Awarded Nov 22, 2021 at 17:40

Clement C.

4,45128 silver badges50 bronze badges

Can we approximate the number of words accepted by an NFA?

Awarded Nov 12, 2021 at 4:31

ricardorr

5415 silver badges14 bronze badges

Does Approx Carathéodory's theorem implies dimensionality reduction

Awarded Nov 4, 2021 at 22:40

Sariel Har-Peled

9,59631 silver badges53 bronze badges

Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

Awarded Nov 2, 2021 at 7:17

Emil Jeřábek

16.9k3 gold badges60 silver badges89 bronze badges

Is there an efficient beta-equivalence algorithm?

Awarded Nov 1, 2021 at 18:35

Damiano Mazza

5,2731 gold badge24 silver badges36 bronze badges

2 3 4 5

…

23 Next