User Samuel Schlesinger

28 votes

2 answers

908 views

Formally Verified Complexity Theory

asked Nov 13, 2017 at 16:25

14 votes

2 answers

750 views

Are There Highly Symmetric NP- or P-complete Languages?

asked Mar 13, 2017 at 21:10

12 votes

1 answer

278 views

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

asked Oct 25, 2017 at 22:05

9 votes

2 answers

179 views

Complexity of Computing Lexicographically Minimal Element of Orbit

asked Mar 12, 2017 at 18:46

9 votes

1 answer

208 views

What is the probability that a random Boolean function has a trivial automorphism group?

asked Jan 24, 2018 at 20:31

9 votes

3 answers

759 views

What are examples of how non-uniformity can be useful?

asked Apr 18, 2018 at 17:16

9 votes

1 answer

250 views

Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?

asked Apr 24, 2018 at 3:19

8 votes

1 answer

268 views

Sampling monotone Boolean functions

asked May 21, 2019 at 17:02

7 votes

1 answer

259 views

What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

asked Sep 18, 2017 at 19:38

6 votes

0 answers

145 views

Has what I am calling "helpfulness" here been studied?

asked Mar 15, 2018 at 20:38

4 votes

1 answer

136 views

Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

asked Mar 2, 2018 at 21:45

4 votes

2 answers

151 views

Is there any notion of sensitivity for probabilistic Boolean functions?

asked Oct 21, 2017 at 18:31

3 votes

0 answers

106 views

Do random functions have synchronous, alternating circuits with non-injective first layers?

asked Nov 18, 2021 at 7:16

2 votes

0 answers

70 views

Can we compute encodings of binary strings under arbitrary permutation groups?

asked Mar 19, 2018 at 22:29

2 votes

2 answers

259 views

One Generalization of Graph Isomorphism Problem

asked Oct 6, 2017 at 4:23

2 votes

0 answers

125 views

What are some known methods for showing that a class has no complete problems?

asked Oct 13, 2017 at 2:24

2 votes

0 answers

87 views

Module Independence Graphs

asked Mar 22, 2017 at 18:38

1 vote

0 answers

234 views

What progress is being made on $NP \cap coNP$ having complete problems? [closed]

asked May 1, 2017 at 0:17

1 vote

0 answers

82 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

asked Nov 1, 2017 at 2:29

1 vote

1 answer

188 views

How good of an approximate 2-coloring can you get of the halved cube graph?

asked Mar 5, 2018 at 9:15

1 vote

1 answer

97 views

What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

asked Feb 2, 2018 at 5:04

1 vote

1 answer

158 views

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

asked Dec 12, 2017 at 1:29

1 vote

0 answers

46 views

Will the maximum entropy joint distribution given a known set of marginal distributions have the maximum plausible support?

asked Oct 15, 2022 at 18:48

-1 votes

1 answer

327 views

What is the connection between adversarial learning in machine learning and program synthesis?

asked Mar 29, 2017 at 18:37

Stack Exchange Network

24 Questions

Formally Verified Complexity Theory

Are There Highly Symmetric NP- or P-complete Languages?

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

Complexity of Computing Lexicographically Minimal Element of Orbit

What is the probability that a random Boolean function has a trivial automorphism group?

What are examples of how non-uniformity can be useful?

Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?

Sampling monotone Boolean functions

What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Has what I am calling "helpfulness" here been studied?

Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

Is there any notion of sensitivity for probabilistic Boolean functions?

Do random functions have synchronous, alternating circuits with non-injective first layers?

Can we compute encodings of binary strings under arbitrary permutation groups?

One Generalization of Graph Isomorphism Problem

What are some known methods for showing that a class has no complete problems?

Module Independence Graphs

What progress is being made on $NP \cap coNP$ having complete problems? [closed]

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

How good of an approximate 2-coloring can you get of the halved cube graph?

What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

Will the maximum entropy joint distribution given a known set of marginal distributions have the maximum plausible support?

What is the connection between adversarial learning in machine learning and program synthesis?