Skip to main content
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
14 votes
Accepted

Connection between PCP and L=SL

3 votes

What is the polynomial representation of the Hamming weight function?

2 votes

Extracting coefficients of polynomials given by straight line programs

5 votes
Accepted

Reference request for linear algebra over GF(2)

1 vote

Does this notion of entropy have a name?

15 votes

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

0 votes

What are some algorithms where space complexity tends to be the limiting factor in practice?

4 votes

Polynomial evaluation at all different points

1 vote

tables of reductions in literature

6 votes

Implications of proving NP=RP on complexity theory

2 votes

Complexity of Set Difference

1 vote
Accepted

Parametrized complexity of sparse optimization

2 votes
Accepted

What kind of computational model is the brain?

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?

12 votes

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

1 vote

Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

8 votes
Accepted

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

1 vote
Accepted

Notation of sequences in rate distortion theory

1 vote
Accepted

Lower bounds on counting functions

6 votes
Accepted

ZPP vs. P status

3 votes
Accepted

Asymptotically good codes

1 vote

Weighted SAT: is this a known problem?

6 votes

Inherent limitation of Switching Lemma for finer lower bounds

4 votes
Accepted

Morgenstern's Theorem

4 votes

A question on the very essence of "theoretical computer science"

9 votes

Author ordering in TCS papers

7 votes
Accepted

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

1 vote

Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially?

3 votes

Surveys on Algorithmic Problems in Coding Theory