Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,368
questions
2
votes
0answers
83 views
Equational Theories for Type Systems
I was reading through Gunter's Semantics of Programming Languages: Structure and Techniques and in the second chapter on simply typed $\lambda$ calculus he introduces an equational theory with $\beta\...
1
vote
0answers
73 views
Fast Computation of First k Eigenvectors of Graph Laplacian
I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$
Algorithm(s) to efficiently estimate the first $k$ (...
2
votes
0answers
172 views
Fast algorithms for evaluating functions with high Kolmogorov complexity
Motivation:
I am motivated by a concrete example that occurs in neuroscience, dendritic computation, which may be approximated by functions computable on binary trees [1]. To be more precise, I ...
1
vote
1answer
122 views
Kolmogorov Complexity of the composition of two computable functions
Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^*$. What I am curious about is whether we can find good upper and lower bounds for:
\begin{equation}...
3
votes
0answers
82 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
14
votes
2answers
996 views
NP-hard problems with very fast exponential-time algorithms
NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.
Is any fact like
"For any constant $\epsilon>0$ there is an NP-hard 'natural' ...
1
vote
0answers
85 views
Weighted circular balls into bins
I would like to ask you for a help about modified balls into bins problem.
Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a ...
5
votes
1answer
174 views
If NP in BPP then NP equals RP
I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:
https://cs.stackexchange.com/q/80509
http://www.inf.ed.ac.uk/teaching/...
7
votes
2answers
153 views
Complexity of graph isomorphism with properly colored edges (ref. request)
An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I ...
5
votes
1answer
176 views
Is this a known problem, and is it #P-complete?
Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges ...
3
votes
0answers
25 views
When was the dynamic array first used as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
6
votes
2answers
143 views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
0
votes
1answer
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 ...
4
votes
0answers
92 views
Reconstructing a colored grid with vertical and horizontal shifts
Consider the following simple problem (puzzle): given
a $N \times N$ $c$-colored grid $G$
a $N \times N$ $c$-colored target grid $G_T$
a number $m$ represented in unary
Can we transform $G$ into $...
1
vote
0answers
63 views
communication complexity lower bound for computing median
In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [...
8
votes
1answer
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 ...
4
votes
0answers
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 ...
0
votes
0answers
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 ...
9
votes
1answer
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 ...
14
votes
1answer
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$ ...
4
votes
0answers
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 ...
8
votes
0answers
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 ...
6
votes
1answer
320 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{...
4
votes
2answers
150 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
254 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
108 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
153 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
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 ...
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
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 ...
9
votes
1answer
197 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
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 ...
2
votes
0answers
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). ...
-1
votes
1answer
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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 ...
4
votes
1answer
107 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
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 ...
2
votes
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 ...
7
votes
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 ...
5
votes
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 ...
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
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 ...
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
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 + ...
5
votes
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 ...
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
83 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
55 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\...
