Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Samuel Schlesinger's user avatar
Samuel Schlesinger's user avatar
Samuel Schlesinger's user avatar
Samuel Schlesinger
  • Member for 7 years, 10 months
  • Last seen more than a month ago
28 votes
2 answers
900 views

Formally Verified Complexity Theory

9 votes
3 answers
750 views

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

14 votes
2 answers
747 views

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

-1 votes
1 answer
325 views

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

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?

7 votes
1 answer
259 views

Sampling monotone Boolean functions

2 votes
2 answers
256 views

One Generalization of Graph Isomorphism Problem

7 votes
1 answer
253 views

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

9 votes
1 answer
249 views

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

1 vote
0 answers
233 views

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

9 votes
1 answer
202 views

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

1 vote
1 answer
187 views

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

9 votes
2 answers
177 views

Complexity of Computing Lexicographically Minimal Element of Orbit

1 vote
1 answer
158 views

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

4 votes
2 answers
148 views

Is there any notion of sensitivity for probabilistic Boolean functions?

6 votes
0 answers
145 views

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

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?

2 votes
0 answers
125 views

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

3 votes
0 answers
106 views

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

1 vote
1 answer
97 views

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

2 votes
0 answers
86 views

Module Independence Graphs

1 vote
0 answers
81 views

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

2 votes
0 answers
70 views

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

1 vote
0 answers
46 views

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