Organizer - Badge - Theoretical Computer Science Stack Exchange

Organizer

First retag.

Awarded 205 times.

Problems complete for non-deterministic PSPACE

Awarded Sep 11 at 9:41

user1868607

9214 silver badges14 bronze badges

Linear Programming Sensitivity to Matrix

Awarded Sep 1 at 23:33

Command Master

4641 silver badge9 bronze badges

Are regular expressions inherently more difficult to construct than DFAs for humans?

Awarded Jan 5 at 9:08

TheDudeAbides

1032 bronze badges

(post deleted or otherwise unavailable)

Awarded Oct 20, 2022 at 10:45

bja

93 bronze badges

Axioms for Shortest Paths

Awarded Mar 29, 2022 at 14:37

Ola Ström

1071 gold badge1 silver badge6 bronze badges

On FFT and trigonometric matrix eigenvalues

Awarded Dec 26, 2021 at 21:25

user1271772

5413 silver badges16 bronze badges

Q: Trusting program output from an untrusted machine

Awarded Dec 5, 2021 at 18:02

Caleb Stanford

8625 silver badges15 bronze badges

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

Awarded Nov 27, 2021 at 21:42

Jake

1,2045 silver badges21 bronze badges

Decidability of transcendental numbers

Awarded Aug 18, 2021 at 23:25

giorgiomugnaini

1032 bronze badges

Is BigInteger-based Brainfuck Turing Complete?

Awarded Jun 30, 2021 at 8:16

Fabian

255 bronze badges

a geometric variant of k-medians. NP-hard or in P?

Awarded Jun 15, 2021 at 8:21

Inuyasha Yagami

1,5311 gold badge7 silver badges25 bronze badges

Are there two definitions of Cobham's thesis?

Awarded Jun 13, 2021 at 8:49

Tien-Cuong Nguyen

1033 bronze badges

How to use Prop from UTT in Agda

Awarded Jun 9, 2021 at 9:35

ice1000

9654 silver badges22 bronze badges

Algorithms Careers

Awarded Apr 28, 2021 at 4:06

Matthieu Latapy

6932 silver badges14 bronze badges

NP complete graph problems about structural properties

Awarded Jan 1, 2021 at 14:36

Blanco

4212 silver badges11 bronze badges

Exact algorithms for $k$-means

Awarded Sep 14, 2020 at 21:05

Christian Komusiewicz

1,70013 silver badges19 bronze badges

What is the proof of this nonstandard version of Azuma's inequality?

Awarded Jul 9, 2020 at 10:35

Miguel Gutierrez

34 bronze badges

Bit complexity of integer factorization?

Awarded Jun 16, 2020 at 9:43

auspicious99

1111 silver badge8 bronze badges

(post deleted or otherwise unavailable)

Awarded Jun 15, 2020 at 8:55

Yonatan N

1,64214 silver badges22 bronze badges

Proof that optimal solutions of LP Relaxation of independent set are half-integral

Awarded Jun 2, 2020 at 7:16

Watercrystal

2571 silver badge9 bronze badges

Minimum cost topological ordering

Awarded May 15, 2020 at 15:46

a3nm

8,91627 silver badges85 bronze badges

Understanding Dudley Chaining Argument for Rademacher Bound

Awarded Feb 29, 2020 at 16:40

Matteo

5693 silver badges14 bronze badges

Problem in deterministic time $n^p$ and not lower

Awarded Feb 4, 2020 at 17:40

Michael Wehar

5,1271 gold badge23 silver badges53 bronze badges

About the decidability of sets enumerated in non decreasing order

Awarded Dec 17, 2019 at 10:15

sixpanbass

1531 silver badge9 bronze badges

(post deleted or otherwise unavailable)

Awarded Sep 21, 2019 at 11:05

VS.

5393 silver badges15 bronze badges

Representations of Planar Graphs in Coq

Awarded Jul 6, 2019 at 8:45

Noam Zeilberger

4,43123 silver badges35 bronze badges

Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

Awarded Jun 23, 2019 at 13:45

Lieuwe Vinkhuijzen

1,95914 silver badges20 bronze badges

Lower bound on the worst-case unbiased coin flips to sample a distribution?

Awarded Jun 7, 2019 at 18:20

Clement C.

4,45128 silver badges50 bronze badges

(post deleted or otherwise unavailable)

Awarded Oct 20, 2018 at 3:40

Mike Shulman

6753 silver badges12 bronze badges

Why it's impossible to declare an induction principle for Church numerals

Awarded Jul 8, 2018 at 18:43

user833970

5462 silver badges10 bronze badges

What are theoretical computer science jobs?

Awarded Jun 6, 2018 at 16:55

usul

7,5951 gold badge25 silver badges45 bronze badges

What precisely is the extra power afforded by using deeper nets?

Awarded May 20, 2018 at 12:29

Łukasz Lew

1,1775 silver badges12 bronze badges

Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

Awarded May 6, 2018 at 16:59

Glorfindel

3571 gold badge4 silver badges10 bronze badges

Is parameterized complexity going to be the future of complexity theory?

Awarded Feb 25, 2018 at 18:20

Thomas

2,80319 silver badges29 bronze badges

Terminology about computation and Finite algebra

Awarded Jan 15, 2018 at 13:48

Michaël Cadilhac

3,94622 silver badges39 bronze badges

The Maxwell's Demon and Computer Science

Awarded Dec 10, 2017 at 14:05

Abhishek Shetty

1486 bronze badges

Is there any notion of sensitivity for probabilistic Boolean functions?

Awarded Oct 25, 2017 at 3:42

Bjørn Kjos-Hanssen♦

4,4752 gold badges25 silver badges40 bronze badges

Solving a "tree-equation"?

Awarded May 22, 2017 at 9:31

holf

2,1641 gold badge15 silver badges20 bronze badges

Is intersection of $k \ge 3$ graphic matroids in P?

Awarded May 15, 2017 at 20:04

Chill2Macht

5033 silver badges13 bronze badges

Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

Awarded Apr 5, 2017 at 8:50

Gamow

5,7726 gold badges24 silver badges39 bronze badges

Connectivity of a random regular graph of degree $d$

Awarded Mar 2, 2017 at 1:50

Devil

4192 silver badges9 bronze badges

Formal semantics of OCaml in Coq

Awarded Feb 28, 2017 at 11:56

gallais

6354 silver badges14 bronze badges

The importance of Integrality Gap

Awarded Dec 7, 2016 at 21:01

Rodrigo de Azevedo

2331 silver badge10 bronze badges

(post deleted or otherwise unavailable)

Awarded Oct 12, 2016 at 9:58

user1105

18113 bronze badges

Is there a certificate definition for polyL?

Awarded Sep 9, 2016 at 7:46

Jan Johannsen

4,6312 gold badges33 silver badges50 bronze badges

Encoding quadratic constraints in a constraint satisfaction problem into SAT

Awarded Sep 5, 2016 at 7:26

ivcha

1869 bronze badges

(post deleted or otherwise unavailable)

Awarded Jul 7, 2016 at 8:47

DCTLib

2642 silver badges7 bronze badges

Is there a survey of the field of quantum automata?

Awarded Apr 7, 2016 at 14:03

Elvin

32 bronze badges

Sorting algorithm with a complexity smaller than $n \log n$?

Awarded Apr 2, 2016 at 22:32

wythagoras

1036 bronze badges

The Average-case Complexity of Simplex Algorithm

Awarded Apr 2, 2016 at 0:07

Minkov

8325 silver badges15 bronze badges

Deeper look at Algorithmica?

Awarded Feb 25, 2016 at 4:04

Martin Schröder

1039 bronze badges

Min Hamming distance of a given string from substrings of another string

Awarded Nov 19, 2015 at 21:33

KWillets

1814 bronze badges

(post deleted or otherwise unavailable)

Awarded Sep 23, 2015 at 22:45

Richard Cox

1194 bronze badges

Compute lowest dimensional polytope from a given set of sign vectors

Awarded Jun 25, 2015 at 14:08

tranisstor

1437 bronze badges

Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

Awarded Jun 19, 2015 at 17:09

Kai

8456 silver badges12 bronze badges

Does L=P imply any new complexity class separations?

Awarded Apr 6, 2015 at 4:11

Stop Harming the Community

1793 bronze badges

Alternative proofs of Schwartz–Zippel lemma

Awarded Mar 31, 2015 at 5:34

Anurag

1907 bronze badges

Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

Awarded Mar 18, 2015 at 8:22

drdiem

33 bronze badges

In which posets is the set of compact elements downwards closed?

Awarded Feb 13, 2015 at 13:11

Damiano Mazza

5,2731 gold badge24 silver badges36 bronze badges

LTL property - safety or liveness?

Awarded Feb 6, 2015 at 19:29

Ratul Saha

1034 bronze badges

2 3 4 Next