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
53 votes
1 answer
2k views

A combinatorial version for the polynomial Hirsch conjecture

43 votes
5 answers
1k views

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

33 votes
4 answers
4k views

Does a noisy version of Conway's game of life support universal computation?

30 votes
1 answer
2k views

Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

29 votes
3 answers
1k views

A Notion of Monotone Quantum Circuits

28 votes
4 answers
1k views

A lottery that you can be convinced that it is fair

27 votes
0 answers
1k views

Counting Isomorphism Types of Graphs

27 votes
2 answers
1k views

Complexity of factoring in number fields

26 votes
1 answer
585 views

Approximately sampling from convex polyhedrons with quantum computers

24 votes
1 answer
512 views

Sampling satisfiable 3-SAT formulas

21 votes
2 answers
1k views

PPAD and Quantum

20 votes
2 answers
644 views

Bounded depth probability distributions

18 votes
1 answer
1k views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

18 votes
0 answers
516 views

Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?

17 votes
0 answers
788 views

Practically Good Algorithms of a Very Low Computational Complexity Class

17 votes
5 answers
404 views

Stronger notions of uniformizations?

17 votes
3 answers
923 views

How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes

15 votes
1 answer
404 views

Triangulating a Planar Polygon

13 votes
1 answer
511 views

Hardness of noisy Boolean functions

11 votes
1 answer
673 views

Quantum algorithms for QED computations related to the fine structure constants

11 votes
1 answer
280 views

To what extent, computational ability for hard tasks helps in solving easy tasks

10 votes
0 answers
249 views

How hard it is to approximate the ground state of the (2-D) Hubbard model

8 votes
1 answer
1k views

States and Probability distributions that the 5-qubits IBM computer can produce

8 votes
0 answers
203 views

Computing permanents when we are promised that the value of the permanent is large