Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi's user avatar
Mahdi Cheraghchi
  • Member for 12 years, 8 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

14 votes
Accepted

Connection between PCP and L=SL

13 votes

From Extractors to Pseudorandom Generators?

12 votes

Why are NPI problems not all of the same complexity?

12 votes

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

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?