Giorgio Camerani's user avatar
Giorgio Camerani's user avatar
Giorgio Camerani's user avatar
Giorgio Camerani
  • Member for 12 years
  • Last seen more than a week ago
377 votes
92 answers
112k views

Algorithms from the Book.

  • 1,855
229 votes
60 answers
95k views

Major unsolved problems in theoretical computer science?

  • 2,213
73 votes
9 answers
16k views

Powerful Algorithms too complex to implement

  • 735
72 votes
4 answers
36k views

Why is 2SAT in P?

  • 1,175
71 votes
17 answers
9k views

Polynomial-time algorithms with huge exponent/constant

  • 454
68 votes
7 answers
4k views

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

62 votes
8 answers
3k views

What is the complexity class most closely associated with what the human mind can accomplish quickly?

  • 5,088
41 votes
5 answers
5k views

What would you advise someone who wants to do research as a hobby?

38 votes
4 answers
1k views

Examples where the uniqueness of the solution makes it easier to find

37 votes
9 answers
2k views

Surprising Results in Complexity (Not on the Complexity Blog List)

  • 11.8k
36 votes
3 answers
941 views

Why does randomness have stronger effect on reductions than on algorithms?

35 votes
17 answers
2k views

Hardness jumps in computational complexity?

33 votes
2 answers
2k views

When does "X is NP-complete" imply "#X is #P-complete"?

33 votes
5 answers
4k views

The unreasonable power of non-uniformity

32 votes
7 answers
10k views

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

  • 4,828
31 votes
4 answers
4k views

Consequences of NP=PSPACE

  • 7,747
28 votes
2 answers
949 views

Tight Lower bounds on Savitch's theorem

  • 1,528
27 votes
2 answers
1k views

Ladner's Theorem vs. Schaefer's Theorem

  • 2,756
27 votes
5 answers
2k views

Long-lasting errors in computer science

  • 121
24 votes
3 answers
5k views

Minimum Unsatisfiable 3-CNF Formulae

  • 249
24 votes
5 answers
2k views

What are some career options for someone with a computer scientist master degree?

  • 853
18 votes
1 answer
2k views

What are the #P-complete subfamilies of #2-SAT?

17 votes
5 answers
3k views

Real world applications of quantum computing (except for security)

14 votes
2 answers
443 views

A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

  • 615
12 votes
1 answer
940 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

9 votes
2 answers
690 views

Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

9 votes
2 answers
541 views

The ODD EVEN DELTA problem

8 votes
1 answer
336 views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

4 votes
1 answer
286 views

How hard is to compute $\Delta_{|V|}$?

3 votes
1 answer
164 views

Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges