Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi
  • Member for 12 years, 6 months
  • Last seen more than 1 year ago
33 votes

Common false beliefs in theoretical computer science

21 votes

Definition of matrix-multiplication exponent $\omega$

19 votes
Accepted

In the neutral zone between polynomial and sub-exponential

16 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

15 votes

What does 'gadget' mean in NP-hard reduction?

14 votes
Accepted

Maximum subset of words with Hamming distance ≥ D

13 votes

From Extractors to Pseudorandom Generators?

13 votes
Accepted

Connection between PCP and L=SL

12 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

12 votes

Why are NPI problems not all of the same complexity?

11 votes
Accepted

"long code test" and "dictatorship test"

10 votes

Problems Between P and NPC

9 votes

Author ordering in TCS papers

8 votes
Accepted

Is the basis of parity functions the only orthonormal basis for Boolean functions?

8 votes

Long-lasting errors in computer science

8 votes

How to find a specific research topic to concentrate on?

8 votes

Are research papers hard to read?

8 votes

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

7 votes
Accepted

Boolean error correcting code over $\mathbb{F}_q$

7 votes
Accepted

Can Polar Codes (or any other efficient codes) reach the second order capacity?

6 votes

Inherent limitation of Switching Lemma for finer lower bounds

6 votes
Accepted

ZPP vs. P status

6 votes

Implications of proving NP=RP on complexity theory

6 votes

Problems with complexity between P and NP that have NP-complete generalizations

6 votes

What's the bias of random polynomials with low degree over GF(2)?

6 votes

Applications of Spectral Graph Theory in Information and Coding Theory

6 votes
Accepted

BPP Error Reduction

5 votes

Not-one 3-SAT; How hard is it?

5 votes
Accepted

Reference request for linear algebra over GF(2)

5 votes

Is 3SAT problem APX-hard or not?