user avatar
user avatar
user avatar
Alessandro Cosentino
  • Member for 11 years, 8 months
  • Last seen this week
5 answers
80 votes
4k views
48 bookmarks
Techniques for Reversing the Order of Quantifiers
12 answers
71 votes
9k views
35 bookmarks
How important is knowing how to program for TCS?
7 answers
68 votes
4k views
31 bookmarks
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
1 answer
65 votes
3k views
26 bookmarks
More on PH in PP?
5 answers
62 votes
4k views
28 bookmarks
Overarching reasons why problems are in P or BPP
0 answers
46 votes
1k views
12 bookmarks
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
2 answers
42 votes
3k views
11 bookmarks
Alphabet of single-tape Turing machine
3 answers
40 votes
2k views
19 bookmarks
Circuit lower bounds over arbitrary sets of gates
7 answers
39 votes
7k views
5 bookmarks
Applicability of Church-Turing thesis to interactive models of computation
4 answers
38 votes
6k views
14 bookmarks
Is $PH \subseteq PP$?
4 answers
38 votes
1k views
9 bookmarks
Examples where the uniqueness of the solution makes it easier to find
5 answers
36 votes
2k views
6 bookmarks
Integer multiplication when one integer is fixed
3 answers
36 votes
936 views
8 bookmarks
Why does randomness have stronger effect on reductions than on algorithms?
2 answers
34 votes
1k views
4 bookmarks
Does LOGLOG = NLOGLOG?
7 answers
32 votes
10k views
25 bookmarks
Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?
3 answers
28 votes
1k views
7 bookmarks
A Notion of Monotone Quantum Circuits
1 answer
28 votes
968 views
6 bookmarks
Is uniform RNC contained in polylog space?
4 answers
28 votes
835 views
5 bookmarks
Complexity of minimising polynomial formula size
1 answer
27 votes
711 views
6 bookmarks
Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
4 answers
27 votes
1k views
3 bookmarks
A lottery that you can be convinced that it is fair
3 answers
27 votes
2k views
11 bookmarks
Cryptography without assumptions -- seeking an overview
5 answers
23 votes
7k views
14 bookmarks
Is there any connection between the diamond norm and the distance of the associated states?
1 answer
21 votes
922 views
6 bookmarks
Algorithms and structural complexity theory
1 answer
20 votes
813 views
8 bookmarks
Consequences of $BQP \subseteq P/poly$?
1 answer
19 votes
950 views
11 bookmarks
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
2 answers
19 votes
1k views
6 bookmarks
Linearly independent Fourier coefficients
11 answers
19 votes
2k views
6 bookmarks
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
0 answers
18 votes
361 views
7 bookmarks
Descriptive complexity of communication complexity classes
2 answers
17 votes
418 views
4 bookmarks
Is PARITY in QAC_0 (if that even makes sense)
1 answer
17 votes
1k views
4 bookmarks
Polynomial speedups with algorithms based on semidefinite programming