Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
157 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
128 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
236 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
227 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
166 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
84 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
126 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
120 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
142 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
109 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
186 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
158 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
252 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
171 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
55 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
29 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
60 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
421 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
108 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
123 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
53 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
93 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\...
2
votes
0answers
63 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,...
3
votes
0answers
71 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 ...
4
votes
2answers
329 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
288 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
324 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
149 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
123 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
54 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,...
1
vote
1answer
97 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
90 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
97 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
649 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 ...
3
votes
1answer
121 views

Estimating inner product over $[r]^d$

Alice has a vector $x \in [r]^d$ and Bob has $y \in [r]^d$, where $[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$. Alice send a message $M(x)$ to Bob and Bob wants to estimate the inner product $\left<...
0
votes
1answer
1k views

Number of simple paths between two vertices in a DAG

Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$. My problem is: how many simple $s-t$...
4
votes
1answer
243 views

Analogue of $k$-wise independence for other distributions than uniform

I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature. Let $D$ be a fixed distribution over $\{0,1\}^n$, and $1\...
0
votes
0answers
63 views

How to get started with program synthesis

I am a CS Major, I am a programmer with 10 years of experience. i want to get to know about program synthesis. there are no video tutorials / courses available online. i have researched about Emina ...
1
vote
0answers
43 views

Stable recovery of signals by $\ell_1$ optimization

Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \...
1
vote
0answers
24 views

Reference request: microbenchmarking

As microbenchmarking is a common method for the performance evaluation, I was expecting it to be extensively researched up to now. The search for related literature has not revealed much, hence I ...
21
votes
2answers
2k views

Languages that we cannot (dis)prove to be Context-Free

I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques. Is there a recent survey on the subject or an open problem ...
10
votes
2answers
279 views

Intuition Behind Strict Positivity?

I'm wondering if someone can give me the intuition behind why strict positivity of inductive data types guarantees strong normalization. To be clear, I see how having negative occurrences leads to ...
1
vote
1answer
70 views

Complexity status of the Edge Deletion problem to bounded degree graphs

I'm interested in the complexity status of the following problem. Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$. Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...
1
vote
0answers
85 views

Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
5
votes
1answer
110 views

$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$. Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, ...
3
votes
2answers
260 views

Extending Hindley-Milner to type mutable references

I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let is used ...
4
votes
0answers
143 views

Is there a standard name for this way of modifying graphs?

Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{...
3
votes
1answer
128 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...

1
2
3 4 5
28