User Niel de Beaudrap

29 votes

2 answers

2k views

What are the consequences of Parity-L = P?

asked Aug 17, 2010 at 17:16

28 votes

0 answers

506 views

Adiabatic quantum computing with level crossings

asked Feb 11, 2012 at 12:48

21 votes

2 answers

2k views

+100

What are the #P-complete subfamilies of #2-SAT?

asked Nov 29, 2012 at 12:49

20 votes

2 answers

932 views

A good reference for complexity class operators?

asked Mar 18, 2014 at 10:32

19 votes

1 answer

583 views

What is the counting complexity of random 2-SAT?

asked Mar 16, 2012 at 20:27

19 votes

1 answer

922 views

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

asked Nov 11, 2011 at 16:28

18 votes

1 answer

783 views

Best known joint containments for/by NP and Parity-P?

asked Aug 17, 2010 at 21:17

16 votes

2 answers

363 views

Finding small sets of integers in which every element is a sum of two others

asked Aug 18, 2010 at 13:51

15 votes

0 answers

1k views

Reference request: a more complete "faster factorization into coprimes"

asked Nov 29, 2010 at 11:52

15 votes

1 answer

298 views

Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

asked Jan 31, 2012 at 16:30

15 votes

1 answer

587 views

Log-space reduction from Parity-L to CNOT circuits?

asked Feb 7, 2012 at 16:24

15 votes

1 answer

725 views

How powerful is exact "quantum" computing if you suspend unitarity?

asked Mar 31, 2014 at 15:26

13 votes

1 answer

348 views

Finding odd holes in circulant Paley graphs

asked Aug 17, 2010 at 15:04

13 votes

1 answer

341 views

Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

asked Apr 22, 2011 at 10:21

13 votes

1 answer

743 views

Circuits with oracles vs. Turing Machines with oracles

asked Aug 25, 2010 at 10:21

13 votes

1 answer

434 views

Efficient algorithm for near-optimal edge-colourings of hypergraphs

asked Sep 6, 2010 at 14:50

11 votes

1 answer

170 views

Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

asked Dec 10, 2014 at 0:30

10 votes

0 answers

194 views

Wide and shallow circuits for $\mathrm P$

asked Aug 24, 2016 at 13:41

9 votes

3 answers

585 views

Submitting other people's work to the arXiv

asked Jul 26, 2012 at 19:46

9 votes

0 answers

115 views

Non-tomographical certification of projectors, using product states?

asked Sep 29, 2011 at 17:45

7 votes

0 answers

134 views

Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

asked Dec 6, 2011 at 17:14

7 votes

1 answer

310 views

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

asked Apr 27, 2014 at 23:27

5 votes

2 answers

199 views

Minimising the root-set of a spanning hyperforest of a hypergraph

asked Jan 23, 2018 at 12:15

Stack Exchange Network

23 Questions

What are the consequences of Parity-L = P?

Adiabatic quantum computing with level crossings

What are the #P-complete subfamilies of #2-SAT?

A good reference for complexity class operators?

What is the counting complexity of random 2-SAT?

Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

Best known joint containments for/by NP and Parity-P?

Finding small sets of integers in which every element is a sum of two others

Reference request: a more complete "faster factorization into coprimes"

Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Log-space reduction from Parity-L to CNOT circuits?

How powerful is exact "quantum" computing if you suspend unitarity?

Finding odd holes in circulant Paley graphs

Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Circuits with oracles vs. Turing Machines with oracles

Efficient algorithm for near-optimal edge-colourings of hypergraphs

Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?

Wide and shallow circuits for $\mathrm P$

Submitting other people's work to the arXiv

Non-tomographical certification of projectors, using product states?

Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

Minimising the root-set of a spanning hyperforest of a hypergraph