Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,354
questions
-1
votes
0answers
51 views
Dependent type theory where branching information informs typing derivations?
In Extensional Martin-Löf type theory (extended with the necessary types) I don't believe the following is derivable
$$
x:\mathbb{N},\,rep:\varPi n:\mathbb{N}.Vec\,n\ \vdash Rec_{\mathbb{B},b.Vec\, x}\...
-1
votes
0answers
9 views
Capacitated Vehicle Routing Problem with multiple pickups at some sites but constrained to max 1 pickup per vehicle per site
I am looking for literature or code for a variant of capacitated vehicle routing problem. The variance is that some sites have multiple items for pickup, but there is a constraint such that even if a ...
4
votes
0answers
60 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 ...
0
votes
0answers
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 ...
9
votes
1answer
119 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 ...
14
votes
1answer
289 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$ ...
3
votes
0answers
75 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 ...
8
votes
0answers
130 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 ...
6
votes
1answer
314 views
On theoretical aproaches for solving $\mathsf{SAT}$ in special cases
In what cases $\mathsf{SAT}$ can be solved in polynomial time?
I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$.
Question 1: Is there a reference with algorithms for solving $\mathsf{...
2
votes
2answers
141 views
What are some good resources for strengthening my theoretical foundation for machine learning?
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
7
votes
3answers
233 views
Can Non-termination be considered an algebraic effect?
Non-termination is sometimes considered an effect. I have been reading about algebraic effect systems (What is algebraic about algebraic effects and handlers?), and I suspect non-termination (like ...
4
votes
1answer
103 views
Satisfiability problems with restricted (not bounded) number of occurrences per variable
Intro
It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly ...
5
votes
1answer
144 views
Counting avoiding improper 3-colorings
Given a graph $G=(V,E)$, what I call an improper $3$-coloring of $G$ is simply a function $c:V \to \{1,2,3\}$. I say that $c$ is $1$-$2$-avoiding when
there do not exist two adjacent nodes $u,v$ with $...
4
votes
0answers
118 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 ...
3
votes
0answers
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 ...
5
votes
1answer
225 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 ...
9
votes
1answer
194 views
Proof for Upper Bound of Sum of Square Roots Problem
In [1], 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$ ...
4
votes
2answers
149 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 ...
2
votes
0answers
76 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). ...
-1
votes
1answer
120 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 ...
2
votes
0answers
109 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 ...
3
votes
1answer
135 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 ...
4
votes
1answer
106 views
A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$
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(...
5
votes
0answers
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 ...
2
votes
1answer
148 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 ...
7
votes
0answers
234 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 ...
5
votes
1answer
167 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 ...
3
votes
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 :...
0
votes
0answers
26 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 ...
0
votes
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....
12
votes
1answer
396 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 + ...
5
votes
1answer
103 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 ...
2
votes
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}...
3
votes
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 ...
7
votes
1answer
78 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 ...
5
votes
0answers
54 views
Hardness result or reference for optimal Gaussian elimination process
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\...
2
votes
0answers
62 views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
2
votes
0answers
59 views
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:
$FPT = XPuniform\implies EPTAS = PTAS$.
Fundamentals of Parametrized complexity on page $534$ has
...
0
votes
0answers
49 views
What is the complexity of Parametric Mixed Integer Linear Programming?
We know
$$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$
$$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$
is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference).
What is ...
4
votes
2answers
321 views
A variant of #POSITIVE-2-DNF
Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations ...
8
votes
1answer
264 views
Is there any quantum analog of the VP vs. VNP problem?
From Wikipedia:
$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\...
4
votes
3answers
287 views
Is counting simple cycles in $P$ for graphs of bounded tree width?
Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ...
7
votes
1answer
142 views
Reference request: Shortest homotopic curve via vertex releases
Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic ...
2
votes
0answers
122 views
A complexity-class of problems that cannot be solved in finite time
Consider the following game: Alice chooses a real function number $x\in [0,1]$; Bob has to guess the number by asking Alice any number of queries of the form "is $x > a$?" [where Bob can choose ...
2
votes
0answers
51 views
Regular Tree Languages are closed under quotient?
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
0
votes
0answers
29 views
Alternating Delivery Problem
What is known about the complexity of the following problem:
Suppose we have a complete bipartite graph $G(V,E)$ with disjoint sets $C$ and $T$. The candidate vertices, and the target vertices ...
1
vote
1answer
95 views
Vehicle scheduling
Suppose there are $n$ resources which can do some work. Each resource has a number of time windows: $tw_{i,k}=\{start_{i, k},stop_{i, k}\}$, such that the resource can perform its functions only ...
3
votes
0answers
89 views
Counting quotient graphs, but not exactly
All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
2
votes
1answer
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 ...
15
votes
1answer
546 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 ...
