Gil Kalai's user avatar
Gil Kalai's user avatar
Gil Kalai's user avatar
Gil Kalai
  • Member for 13 years, 7 months
  • Last seen more than a week ago
37 votes

What would it mean to disprove Church-Turing thesis?

34 votes

Applications of TCS to classical mathematics?

24 votes

Coloring Planar Graphs

21 votes

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

18 votes
Accepted

Complex analysis in theoretical computer science

17 votes

Quantum computing project ideas

15 votes

Major unsolved problems in theoretical computer science?

15 votes

Overarching reasons why problems are in P or BPP

14 votes

Examples of the price of abstraction?

13 votes

Intractability of NP-complete problems as a principle of physics?

13 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

12 votes

Reasons for which a graph may be not $k$ colorable?

12 votes

Applications of representation theory of the symmetric group

12 votes

Conjectures implying Four Color Theorem

11 votes

Reasons for which a graph may be not $k$ colorable?

11 votes

Extension to the Stable Marriage Problem ?

10 votes

Applications of TCS to classical mathematics?

10 votes

The cozy neighborhoods of "P" and of "NP-hard"

9 votes

Are edge-vertex graphs of polytopes (decent) expanders?

9 votes

Maximal/maximum independent sets

8 votes

Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

7 votes

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

6 votes

Rigour leading to insight

6 votes

Applications of TCS to classical mathematics?

6 votes

Using error-correcting codes in theory

6 votes

Information Theory used to prove neat combinatorial statements?

6 votes

Complex analysis in theoretical computer science

5 votes

Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

5 votes

Complex analysis in theoretical computer science

2 votes

Information Theory used to prove neat combinatorial statements?