Skip to main content
Theoretical Computer Science
Mark S's user avatar
Mark S's user avatar
Mark S's user avatar
Mark S
  • Member for 7 years
  • Last seen this week
Profile Activity
Stats
1,145
reputation
11k
reached
13
answers
16
questions
Communities
View all
About
Hi, I'm just an amateur. I've been lurking for a while. I answered a question, some nice people voted up my answer and I appreciate it, so now creating an account.
Badges
View all badges
This user doesn’t have any gold badges yet.
6
silver badges
20
bronze badges
Top tags
View all tags
18
Score
9
Posts
31
Posts %
11
Score
11
Posts
38
Posts %
8
Score
3
Posts
10
Posts %
5
Score
2
Posts
7
Posts %
4
Score
2
Posts
7
Posts %
3
Score
4
Posts
14
Posts %
Top posts
View all questions and answers
question
13
Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?
Dec 24, 2017
question
9
What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?
Aug 31, 2017
answer
8
Knot Recognition as a Proof of Work
Sep 27, 2017
question
7
What is the complexity of estimating the number of paths between two vertices of a large graph?
Jul 27, 2020
question
5
(Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?
Apr 24, 2023
answer
5
Problems in NP with non-trivial certificate
Jun 21, 2023
answer
4
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
May 28, 2023
question
4
Does Rush-Hour (or Klotski) admit a search-to-decision reduction?
May 12
question
4
If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?
Mar 21, 2018
question
3
On "The Power of the Prover" in Arora and Barak
Apr 25, 2018
Top network posts
View all network posts
123
What are some noteworthy "mic-drop" moments in math?
49
Pseudonyms of famous mathematicians
48
Have the tides ever turned twice on any open problem?
46
What recent discoveries have amateur mathematicians made?
34
Can we three-color a tiling of the plane with Smith, Meyers, Kaplan, and Goodman-Strauss's einstein?