Revival - Badge - Theoretical Computer Science Stack Exchange

Revival

Answer more than 30 days after a question was asked as first answer scoring 2 or more. This badge can be awarded multiple times.

Awarded 627 times.

Reductions and projections in circuit complexity

Awarded yesterday

Eric Allender

1,30614 silver badges10 bronze badges

What circuit depth is enough to compute a log-space complete problem?

Awarded 2 days ago

Eric Allender

1,30614 silver badges10 bronze badges

Problems complete for non-deterministic PSPACE

Awarded Sep 20 at 17:35

Hermann Gruber

5,7611 gold badge32 silver badges57 bronze badges

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

Awarded Sep 13 at 3:32

Eric Allender

1,30614 silver badges10 bronze badges

Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?

Awarded Aug 9 at 18:21

sparusaurata

997 bronze badges

Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Awarded Aug 6 at 19:46

Niranjan Kumar

362 bronze badges

Can an unrestricted grammar have a rule with only terminals on the left-hand side?

Awarded Aug 6 at 11:03

Belek Omurzakov

212 bronze badges

Transitive reduction not provably minimal

Awarded Jul 28 at 14:57

Mark Amery

1215 bronze badges

Short UNSAT Certificates for X3SAT

Awarded Jul 13 at 8:25

Russell Easterly

5492 silver badges10 bronze badges

How hard is Hex from a symmetric position?

Awarded Jul 1 at 15:06

Kevin Wang

1566 bronze badges

On parallel complexity of modular inverse

Awarded May 8 at 23:06

Emil Jeřábek

16.5k3 gold badges58 silver badges88 bronze badges

Semantic read-back of sharing graphs

Awarded May 5 at 18:56

Beniamino Accattoli

3412 silver badges4 bronze badges

Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

Awarded Apr 28 at 14:47

user69092

193 bronze badges

Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution

Awarded Apr 21 at 0:02

Jxb

1659 bronze badges

Kleisli-like category for applicatives?

Awarded Apr 20 at 14:41

Max New

1,6388 silver badges23 bronze badges

Hashing-based vs almost uniform sampling-based approximate counting

Awarded Mar 28 at 17:06

Kuldeep Meel

212 bronze badges

Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

Awarded Mar 17 at 16:11

Glenn Tang

312 bronze badges

How far is the distance between Mahlo Universe and Mahlo Cardinal?

Awarded Feb 25 at 5:10

Ember Edison

516 bronze badges

Circuit Complexity Charaterization for DLogTime and NLogTime

Awarded Feb 9 at 20:07

Emil Jeřábek

16.5k3 gold badges58 silver badges88 bronze badges

Maximizing difference of a submodular and a modular function

Awarded Feb 7 at 18:57

dohmatob

2911 silver badge12 bronze badges

Polynomial convergence to optimal move of the UCT algorithm. Missing proof?

Awarded Jan 31 at 23:03

Zach

1013 bronze badges

Most efficient inplace merge algorithms (stable and unstable)

Awarded Jan 31 at 1:09

Guest

761 silver badge4 bronze badges

Proving P-Isomorphism between two languges

Awarded Jan 30 at 17:26

Joshua Grochow

36.7k4 gold badges128 silver badges227 bronze badges

Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

Awarded Nov 30, 2022 at 2:33

Wei Zhan

7235 silver badges17 bronze badges

Is there any context-free language that is inherently ambiguous as an indexed language

Awarded Nov 22, 2022 at 12:26

Hermann Gruber

5,7611 gold badge32 silver badges57 bronze badges

Is there any inherently ambiguous indexed language?

Awarded Nov 22, 2022 at 7:49

Hermann Gruber

5,7611 gold badge32 silver badges57 bronze badges

A super-linear time problem in NL

Awarded Nov 6, 2022 at 11:12