# Questions tagged [reference-request]

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

1,368 questions
Filter by
Sorted by
Tagged with
83 views

149 views

### A Simple Auction Game

You are playing the following game. You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a ...
92 views

357 views

### PHOAS with extrinsic typing?

Parameterized Higher Order Abstract Syntax (PHOAS) is a representation of syntax trees that allows the host language's binding to be used to represent binding in the language being modelled, while ...
61 views

### Short $\exists$SO sentences over strings that define an NP-complete problem

[Q1] I'm wondering if there are some "official" SHORT existential second order sentences with ONE binary relation, over strings (over a small alphabet) that define an NP-complete set. (Something ...
45 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 ...
121 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 ...
319 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$ ...
92 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 ...
142 views

### A canonical complete problem for EXP and NEXP in terms of formulae

3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE. Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
320 views

121 views

### Characterizing the ANF of Single-Cycle Boolean Permutations

Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
110 views

### Earliest forbidden subgraph characterisation

I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ? Of course, bipartite graph is one example but I am considering it as trivial ...
228 views

### The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows: $$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$ Apparently, Knuth was able to prove that ...
197 views

### Proof for Upper Bound of Sum of Square Roots Problem

In , Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP. Given integers $a_1, a_2, \ldots, a_n$ ...
160 views

### reference request for construction of expanders

I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
77 views

### Common techniques for the acyclic orientation problem under some special constraint?

An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
123 views

### Gödel-Numbering of the Context-Sensitive Languages

I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
111 views

### Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...
138 views

### The theory of definitions in first order logic

I'm looking for a clear and thorough treatment of the theory of definitions in first order predicate logic from a syntactic/proof theoretic point of view (as opposed to semantic/model theoretic point ...
107 views

First order logic comes equipped with two kinds of terms: Variable: those terms of the form $x$ for some variable $x$, of which there are infinite. Function application: those terms of the form $f(... 0answers 181 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 ... 1answer 157 views ### Possibility of hierarchy with$UP$class? I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with$NP$and$coNP$and leads up to$PSPACE$. The ... 0answers 245 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 ... 1answer 169 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 ... 0answers 53 views ### Algorithms for Maximum weight connected subgraph in planar graphs I wonder what is known about the two following maximisation problems. Maximum weight connected subgraph : Input : A graph$G$, with weights$w_v\in \mathbb{R}$for each vertex$v \in V(G)$Output :... 0answers 27 views ### Two question regarding coreset construictions I have two questions regarding coreset construction of clustering problem In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for ... 0answers 57 views ### Linear time algorithm for projective clustering There is a lot of work in clustering of high dimensional data. In case of k-means, it is shown here that one can get an$(1+\epsilon)$-approximation in linear time, yielding a PTAS, by random sampling.... 1answer 398 views ### Deterministic error reduction, state-of-the-art? Assume one has a randomized (BPP) algorithm$A$using$r$bits of randomness. Natural ways to amplify its probability of success to$1-\delta$, for any chosen$\delta>0$, are Independent runs + ... 1answer 104 views ### k-testable languages with non-constant k? Let$p_t(w)$and$s_t(w)$denote the prefix and suffix of length$t$of the word$w$, respectively. If$|w| < t$, then$p_t(w) = s_t(w) = w$. Furthermore, let$i_t(w)$be the set of infixes of ... 1answer 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}... 0answers 50 views ### Hardness of Approximation of Set Cover with Growing Size Bound I'm considering the minimum set cover problem with the constraint that each set contains at most$k$elements. Here,$k$depends on the size of the universe. For example,$k$may equal$\log n,\sqrt ...
I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome. Input: integers $n\geq1,k\geq0$ and an invertible matrix \$M\in\...