user avatar
user avatar
user avatar
Samuel Schlesinger
  • Member for 6 years
  • Last seen more than a month ago
27 votes
2 answers
818 views

Formally Verified Complexity Theory

14 votes
2 answers
733 views

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

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?

9 votes
2 answers
168 views

Complexity of Computing Lexicographically Minimal Element of Orbit

9 votes
1 answer
192 views

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

9 votes
3 answers
695 views

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

9 votes
1 answer
221 views

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

7 votes
1 answer
211 views

Sampling monotone Boolean functions

7 votes
1 answer
247 views

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

6 votes
0 answers
143 views

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

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?

4 votes
2 answers
145 views

Is there any notion of sensitivity for probabilistic Boolean functions?

3 votes
0 answers
98 views

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

2 votes
0 answers
70 views

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

2 votes
2 answers
247 views

One Generalization of Graph Isomorphism Problem

2 votes
0 answers
125 views

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

2 votes
0 answers
85 views

Module Independence Graphs

1 vote
0 answers
229 views

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

1 vote
0 answers
76 views

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

1 vote
1 answer
155 views

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

1 vote
1 answer
85 views

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

1 vote
1 answer
150 views

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

0 votes
0 answers
26 views

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

-1 votes
1 answer
320 views

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