# Questions tagged [reference-request]

Reference-request is used when the author needs to know about work related to the question.

1,344 questions
Filter by
Sorted by
Tagged with
78 views

### Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
104 views

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

Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$. Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, ...
206 views

### Extending Hindley-Milner to type mutable references

I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let is used ...
143 views

436 views

### Proof techniques for showing that dependent type checking is decidable

I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
190 views

Do any of you know a reference for the following (surprisingly tedious to prove) result? Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \... 1answer 218 views ### Fast algorithm to find a maximum connected subgraph of k vertices Given an undirected graph$G = (V, E)$and a function$f: 2^V \to \mathbb{R}^+,$where$2^V$is the set of all subsets of$V$. Find a connected subgraph$T = (V_T, E_T)$of k vertices such that$f(V_T)...
Straight to the point: I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the ...