User Gil Kalai

53 votes

1 answer

2k views

A combinatorial version for the polynomial Hirsch conjecture

asked Sep 30, 2010 at 13:56

43 votes

5 answers

1k views

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

asked Dec 22, 2012 at 16:58

33 votes

4 answers

4k views

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

asked Jun 5, 2013 at 17:49

31 votes

1 answer

2k views

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

asked Nov 26, 2010 at 9:49

30 votes

3 answers

1k views

A Notion of Monotone Quantum Circuits

asked Sep 11, 2012 at 9:59

28 votes

4 answers

1k views

A lottery that you can be convinced that it is fair

asked Jun 15, 2012 at 16:15

27 votes

0 answers

1k views

Counting Isomorphism Types of Graphs

asked Sep 29, 2013 at 3:07

27 votes

2 answers

1k views

Complexity of factoring in number fields

asked Jan 24, 2013 at 16:17

26 votes

1 answer

593 views

Approximately sampling from convex polyhedrons with quantum computers

asked Dec 14, 2010 at 19:45

25 votes

1 answer

520 views

Sampling satisfiable 3-SAT formulas

asked Sep 1, 2013 at 18:18

21 votes

2 answers

1k views

PPAD and Quantum

asked Sep 8, 2019 at 11:32

20 votes

2 answers

645 views

Bounded depth probability distributions

asked Nov 29, 2012 at 23:05

18 votes

1 answer

1k views

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

asked Apr 28, 2013 at 20:49

18 votes

0 answers

518 views

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

asked May 13, 2015 at 6:58

17 votes

0 answers

788 views

Practically Good Algorithms of a Very Low Computational Complexity Class

asked Nov 3, 2014 at 6:14

17 votes

5 answers

405 views

Stronger notions of uniformizations?

asked Sep 23, 2010 at 21:30

17 votes

3 answers

927 views

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

asked Aug 17, 2011 at 8:24

15 votes

1 answer

404 views

Triangulating a Planar Polygon

asked Aug 29, 2010 at 11:05

13 votes

1 answer

513 views

Hardness of noisy Boolean functions

asked Sep 1, 2013 at 17:46

11 votes

1 answer

692 views

Quantum algorithms for QED computations related to the fine structure constants

asked Dec 17, 2014 at 10:48

11 votes

1 answer

280 views

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

asked Aug 10, 2015 at 13:04

10 votes

0 answers

255 views

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

asked Jan 19, 2014 at 4:01

8 votes

1 answer

1k views

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

asked Jun 8, 2016 at 18:56

8 votes

0 answers

207 views

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

asked May 14, 2022 at 17:15

Stack Exchange Network

24 Questions

A combinatorial version for the polynomial Hirsch conjecture

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

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

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

A Notion of Monotone Quantum Circuits

A lottery that you can be convinced that it is fair

Counting Isomorphism Types of Graphs

Complexity of factoring in number fields

Approximately sampling from convex polyhedrons with quantum computers

Sampling satisfiable 3-SAT formulas

PPAD and Quantum

Bounded depth probability distributions

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

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

Practically Good Algorithms of a Very Low Computational Complexity Class

Stronger notions of uniformizations?

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

Triangulating a Planar Polygon

Hardness of noisy Boolean functions

Quantum algorithms for QED computations related to the fine structure constants

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

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

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

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