User Samuel Schlesinger

27 votes

2 answers

818 views

Formally Verified Complexity Theory

asked Nov 13, 2017 at 16:25

14 votes

2 answers

733 views

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

np algebra gr.group-theory complexity symmetry

asked Mar 13, 2017 at 21:10

12 votes

1 answer

266 views

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

graph-theory graph-isomorphism formulas first-order-logic

asked Oct 25, 2017 at 22:05

9 votes

2 answers

168 views

Complexity of Computing Lexicographically Minimal Element of Orbit

permutations gr.group-theory complexity

asked Mar 12, 2017 at 18:46

9 votes

1 answer

192 views

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

boolean-functions randomness gr.group-theory symmetry

asked Jan 24, 2018 at 20:31

9 votes

3 answers

695 views

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

circuit-complexity advice-and-nonuniformity

asked Apr 18, 2018 at 17:16

9 votes

1 answer

221 views

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

boolean-functions fourier-analysis

asked Apr 24, 2018 at 3:19

7 votes

1 answer

211 views

Sampling monotone Boolean functions

boolean-functions sample-complexity monotone

asked May 21, 2019 at 17:02

7 votes

1 answer

247 views

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

np-hardness lower-bounds

asked Sep 18, 2017 at 19:38

6 votes

0 answers

143 views

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

reference-request circuit-complexity boolean-functions

asked Mar 15, 2018 at 20:38

4 votes

1 answer

134 views

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

circuit-complexity lower-bounds parity

asked Mar 2, 2018 at 21:45

4 votes

2 answers

145 views

Is there any notion of sensitivity for probabilistic Boolean functions?

circuits probabilistic-circuits

asked Oct 21, 2017 at 18:31

3 votes

0 answers

98 views

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

circuit-complexity boolean-functions boolean-formulas circuits circuit-depth

asked Nov 18, 2021 at 7:16

2 votes

0 answers

70 views

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

permutations gr.group-theory circuits

asked Mar 19, 2018 at 22:29

2 votes

2 answers

247 views

One Generalization of Graph Isomorphism Problem

graph-theory graph-algorithms graph-isomorphism

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?

cc.complexity-theory np p-vs-np

asked Oct 13, 2017 at 2:24

2 votes

0 answers

85 views

Module Independence Graphs

finite-fields

asked Mar 22, 2017 at 18:38

1 vote

0 answers

229 views

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

cc.complexity-theory open-problem

asked May 1, 2017 at 0:17

1 vote

0 answers

76 views

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

quantum-computing circuit-complexity quantum-information probabilistic-circuits

asked Nov 1, 2017 at 2:29

1 vote

1 answer

155 views

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

graph-theory boolean-functions graph-colouring approximation

asked Mar 5, 2018 at 9:15

1 vote

1 answer

85 views

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

kolmogorov-complexity permutations gr.group-theory symmetry

asked Feb 2, 2018 at 5:04

1 vote

1 answer

150 views

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

quantum-computing circuit-complexity

asked Dec 12, 2017 at 1:29

0 votes

0 answers

26 views

Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?

cc.complexity-theory circuit-complexity circuits circuit-depth

asked Nov 18, 2021 at 7:43

-1 votes

1 answer

320 views

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

cc.complexity-theory ds.algorithms machine-learning adversarial-learning

asked Mar 29, 2017 at 18:37

Stack Exchange Network

current community

your communities

more stack exchange communities

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?

Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?

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