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
36 votes
3 answers
4k views

Consequences of Factoring being in P?

34 votes
2 answers
2k views

Consequences of $SAT \in BQP$

26 votes
3 answers
2k views

Consequences of #P = FP

21 votes
10 answers
3k views

#SAT Solver download

21 votes
5 answers
3k views

Reasons for which a graph may be not $k$ colorable?

19 votes
3 answers
2k views

Shortest Equivalent CNF Formula

18 votes
5 answers
692 views

Unique $k$-SAT benchmarks

17 votes
2 answers
931 views

Lower bounds on #SAT?

15 votes
4 answers
2k views

Counting the number of vertex covers: when is it hard?

14 votes
2 answers
1k views

0-1 Linear Programming: computing the Optimal Formulation

13 votes
2 answers
1k views

Counting solutions of Monotone-2CNF formulas

12 votes
1 answer
400 views

Measuring the randomness of CNF formulas

12 votes
1 answer
940 views

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

12 votes
1 answer
1k views

Consensus on P = NP in a world where RP = NP

11 votes
3 answers
799 views

Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

10 votes
2 answers
472 views

Compactly representing the solution set of a SAT instance

10 votes
2 answers
555 views

Amplitude of Random Cubic Graphs

9 votes
2 answers
541 views

The ODD EVEN DELTA problem

9 votes
1 answer
532 views

Help on the following combinatorial problem?

9 votes
2 answers
2k views

Reducing #SAT to #MONOTONE-2SAT

9 votes
2 answers
690 views

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

8 votes
2 answers
556 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

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$

8 votes
2 answers
547 views

Using SAT for Computer Vision tasks

8 votes
2 answers
3k views

Monotone-2SAT and Vertex Cover

7 votes
2 answers
586 views

SAT Solution Space - Definition of Cluster of Solutions

7 votes
1 answer
309 views

Determining Graph Hulls

7 votes
4 answers
1k views

Trees: complexity of counting the number of vertex covers

7 votes
1 answer
428 views

Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

7 votes
2 answers
310 views

How hard is counting the number of vertex covers after a small perturbation?