Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Elle Najt's user avatar
Elle Najt's user avatar
Elle Najt's user avatar
Elle Najt
  • Member for 7 years, 1 month
  • Last seen more than a week ago
5 votes
0 answers
85 views

Chosen message attack on unhashed GGH signatures?

1 vote
1 answer
173 views

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

6 votes
1 answer
263 views

Uniformly sampling or counting connected graph partitions with any number of blocks

7 votes
0 answers
123 views

Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?

10 votes
0 answers
177 views

Alternative proofs of Savitch's theorem?

10 votes
0 answers
163 views

Is counting the total number of faces of a polytope $\#P$ hard?

14 votes
0 answers
232 views

Counting solutions to extended MSO formulas, and sampling -- do these appear in the literature?

2 votes
0 answers
47 views

"Planar graph coloring is not self-reducible" is this about all $p$-relations encoding that problem?

3 votes
0 answers
72 views

Problem of determining if a $4$ connected graph has $k$ Hamiltonian cycles

5 votes
3 answers
484 views

Is counting simple cycles in $P$ for graphs of bounded tree width?

15 votes
1 answer
798 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

5 votes
1 answer
114 views

$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

8 votes
3 answers
407 views

Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

4 votes
1 answer
346 views

Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

2 votes
1 answer
182 views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

5 votes
1 answer
170 views

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

4 votes
1 answer
181 views

NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

5 votes
1 answer
473 views

Distributions which are intractable to sample from?

6 votes
2 answers
587 views

Max cut problem between two connected subgraphs

8 votes
0 answers
278 views

How to sample a lot of independent uniform spanning trees?