Professor of Mathematics at the Hebrew University of Jerusalem and at Yale University
|
Jun
15 |
|
comment |
Does a noisy version of Conway's game of life support universal computation? Peter, if your computation succeed with probability 2/3, I am happy. |
|
Jun
12 |
|
revised |
Does a noisy version of Conway's game of life support universal computation? added 249 characters in body |
|
Jun
11 |
|
awarded | Nice Question |
|
Jun
8 |
|
comment |
Does a noisy version of Conway's game of life support universal computation? The real question here is if the stochastic/noisy versions of the "Game of Life" still support computation. (If these version support computations in P then their power may go all the way to BPP.) It is possible that the computational power of these stochastic versions of the game of life is much lower. |
|
Jun
5 |
|
asked | Does a noisy version of Conway's game of life support universal computation? |
|
May
5 |
|
comment |
The complexity of sampling (approximately) the Fourier transform of a Boolean function BTW, Scott, isn't the argument via permanents that shows that BOSONSAMPLING in BPP implies collapse of the PH works also for Fourier sampling? |
|
May
4 |
|
revised |
The complexity of sampling (approximately) the Fourier transform of a Boolean function added 1242 characters in body |
|
May
4 |
|
comment |
The complexity of sampling (approximately) the Fourier transform of a Boolean function Thanks, Scott, thhis is very interesting. I will mention your conjecture along with a few others in the next edit of the question. |
|
May
3 |
|
revised |
The complexity of sampling (approximately) the Fourier transform of a Boolean function added 17 characters in body |
|
May
2 |
|
awarded | Supporter |
|
May
2 |
|
revised |
The complexity of sampling (approximately) the Fourier transform of a Boolean function added 529 characters in body |
|
May
1 |
|
comment |
Count the number of spanning trees fast Doing Linear algebra with the Laplacian rather than a general matrix is often easier. I wonder if this can be relevant. |
|
Apr
30 |
|
awarded | Nice Question |
|
Apr
29 |
|
comment |
The complexity of sampling (approximately) the Fourier transform of a Boolean function Thanks, Martin! I suppose it is not known how hard it is to sample from the Fouriet transform even of AC^0 functions, right? (In the case of depth-2 a conjecture of Mansour asserts that it is polynomial (with randomization). |
|
Apr
28 |
|
asked | The complexity of sampling (approximately) the Fourier transform of a Boolean function |
|
Feb
21 |
|
awarded | Good Question |
|
Feb
20 |
|
awarded | Necromancer |
|
Feb
10 |
|
answered | Complex analysis in theoretical computer science |
|
Jan
31 |
|
awarded | Nice Answer |
|
Jan
29 |
|
revised |
Complexity of factoring in number fields added 771 characters in body |
