Reputation
3,085
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
2 19 39
Newest
 Necromancer
Impact
~240k people reached

Mar
30
comment Question about non-private databases and $1^n$
en.wikipedia.org/wiki/Security_parameter
Feb
25
comment Deeper look at Algorithmica?
I think the reason this hasn't been explored more is that it's hard to imagine what a conditional result in algorithmica would look like past what Ricky said.
Jan
22
comment Why hidden subgroup problem is easy for very large subgroup?
@OmarShehab: en.wikipedia.org/wiki/Index_of_a_subgroup
Jan
18
comment Constructive proof of the Halting Problem
I think you misunderstood Sipser. He uses diagonalization to show that there exists some undecidable language, and then proves (not using diagonalization) that the halting problem in particular is undecidable.
Jan
18
comment Constructive proof of the Halting Problem
I think this is a duplicate of cstheory.stackexchange.com/questions/3810/…
Dec
6
revised Voronoi Diagram of Lines
edited body
Dec
6
answered Voronoi Diagram of Lines
Nov
29
revised When does adding edges decrease the cover time of a graph?
added 4 characters in body
Nov
25
comment Does solving matrix multiplication in quadratic time imply that SETH is false?
@MichaelWehar: Thanks for the link! Maybe that would be worth adding as an addendum to your post?
Nov
19
comment Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic
I don't understand what you mean by an "FPT NP-complete language". There's no natural notion of a language by itself being FPT; the question is whether a language/parameter pair is FPT.
Nov
16
comment Big picture in counting complexities
Could you please provide a reference for the "$\tau$"-conjecture?
Nov
16
reviewed Approve Surveys on pseudo-random number generator design?
Nov
15
reviewed Approve Papers on relation between computational complexity and algebraic geometry/topology?
Nov
15
reviewed Approve What kind of mathematical background is needed for complexity theory?
Nov
13
comment Quantum Hardness of Approximating Lattice Problems
@Chris: Thanks for the comment. Citation added.
Nov
13
revised Quantum Hardness of Approximating Lattice Problems
Added additional citation
Nov
11
comment One way functions and $NP\cap coNP$
@EmilJeřábek: I agree that the question is not completely well-formed, but I think you understand what he means. It's a valid observation that the decision variants of factoring, discrete log, and gap-lattice problems with polynomial approximation factors -- the main problems from which we derive candidate OWFs -- are in $NP \cap coNP$.
Nov
11
comment One way functions and $NP\cap coNP$
Why are people downvoting this? I think it's a fine question.
Nov
6
reviewed Approve Two DFA intersection emptiness connections to SETH & L vs P
Nov
5
reviewed Approve What are the relationships between those hypotheses in Fine-Grained Complexity Theory?