The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [reference-request]

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

1,351 questions
Filter by
Sorted by
Tagged with
511 views

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

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
40 views

### Incompleteness and term extraction

Is there a formalization, which from a proof that a system includes enough arithmetic extracts an arithmetic sentence in the language of PA, which is not provable in the given system? Imagine the ...
269 views

### Why is the Greedy Conjecture so difficult?

I recently learned about the Greedy conjecture for the Shortest Superstring Problem. In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ ...
117 views

### The source of the modular decomposition graph

When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia. The question is who is (are) the original designer of it. (I'm not asking who drew ...
73 views

### Eliminating tautological axioms in tree-like $k$-DNF resolution

The propositional proof system $k$-DNF-resolution, a.k.a. $Res(k)$, is a generalization of propositional resolution, where the lines in a proof are $k$-DNF formulas, i.e., disjunctions of $k$-terms of ...
305 views

685 views

### Online Algorithms books

Are there any recent books on Online Algorithms? I know of only two books on the subject. Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old book,...
143 views

178 views

### Generalization of Element Distinctness

In the element distinctness problem, one has query access to an arbitrary multiset of $n$ elements and must decide whether they are all distinct. From a property testing point of view, the question ...
233 views

### Reverse Skolemization?

I'm wondering if there are any references on "reverse skolemization", that is, converting a formula with functions into one purely consisting of quantifiers by eliminating function applications. I'm ...
122 views

### Lower bound on the worst-case unbiased coin flips to sample a distribution?

Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:  \Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}...
166 views

### Does the following type of hitting problem have a name?

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
92 views

### References on generalization bounds

I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or ...
221 views

75 views

### Simple proof that splay trees have the dynamic finger property?

Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ...
In "A Really Temporal Logic", by R.Alur and A.Henziger, they introduce an extension of Linear Temporal Logic with a freeze quantifier $x.\phi$, which allows to "give a name" to the current time point ...