# Questions tagged [reference-request]

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

1,639 questions
Filter by
Sorted by
Tagged with
180 views

98 views

### Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
1 vote
154 views

### In what paper did Dijkstra say "with your hands in your pockets"?

I'm looking for a paper by Edsger Dijkstra (which I've read before) in which he talks about a certain mathematical argument that I can't quite remember what it was, but it was an elementary strategy ...
201 views

### The empty tree-word for regular tree languages

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word? ...
366 views

### What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
130 views

641 views

### Complexity of NFA cofiniteness

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)? Surely this must be known but I can't find a reference. Note that the ...
1 vote
41 views

### Convergence rates for the iterates of SGD on Lipschitz convex functions

Let $f:X \rightarrow \mathbb{R}$ be a convex and $L$-Lipschitz continuous function. Suppose $f^* = \min_{x \in X} f(x) \in \mathbb{R}$ and let $X^* = \{x \in X : f(x) = f^*\}$. For a non-negative ...
101 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
307 views

### Cheap online selection with weighted comparisons

Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$. We do not have access to the values of these elements, but we can compare any two elements of $S$...
21 views

### Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
76 views

### References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
41 views

### Characterization of CF languages closed under circular shifts

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts? Are there simple characterizations/properties of Context Free ...
226 views

### Horn clause on cnf

Recall that a CNF formula is Horn if each clause contains at most one positive literal. Is it possible any unsatisfiable Horn CNF formula has a polynomial-size treelike Resolution refutation? Is there ...
40 views

### Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
88 views

### Learning discrete math for research

This might be an unusual question, but please bear with me. As a graduate student in mathematics, I haven't delved deeply into several discrete math subjects relevant to research in theoretical ...
256 views

### How many numbers are needed such that the possible subset sums cover $\{1, \frac{1}{2}, \frac{1}{3},\dots, \frac{1}{2^m}\}$?

For a multiset $N$ of positive numbers, the set of possible subset sums is $f(N)=\{s\in \mathbb{R}: \exists S\in 2^N, s=\sum_{a\in S} a\}$. We say $N$ generates $T$ if $T\subseteq f(N)$. For example, ...
191 views

### Calculation on Sparsification and critical clauses in SAT

I followed from this question. I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$ But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$. ...
1 vote
49 views

### Short learned clauses for XSAT

Are there any studies about how effective a limited resolution pre-processor is for DPLL-CDCL type SAT solvers? By limited resolution pre-processor I mean a pre-processor that generates short (1,2, or ...
194 views

### What infinite sums cannot be approximated in polynomial time?

The following is from the book Geometric algorithms and combinatorial optimization: It shows an infinite sum that has an FPTAS (= an $\epsilon$-approximation can be computed using poly($1/\epsilon$) ...
81 views

### On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
1 vote
323 views

### Sparsification and critical clauses in SAT

I have been studying the Exponential-Time Hypothesis, ETH, from this paper, there defined $s_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$. But in that paper's page number 10, I ...
151 views

### What is best lower bound for comparison sort?

Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term. What is the best known lower bound for large $n$? I couldn't ...