Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [reference-request]

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

3
votes
0answers
21 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\...
1
vote
0answers
30 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,...
1
vote
0answers
50 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
40 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
176 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
213 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$. $\...
3
votes
2answers
132 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
113 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
111 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
46 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
27 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
88 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
81 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
0answers
66 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 ...
13
votes
1answer
416 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 ...
2
votes
1answer
100 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
150 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
141 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
54 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
38 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
23 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
1k 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 ...
0
votes
0answers
34 views

Reference on generalization of plane graph duality between bonds and simple cycles

I've also asked this question on Mathoverflow, but it hasn't gotten an answer after several months: https://mathoverflow.net/questions/316132/reference-on-generalization-of-plane-graph-duality-between-...
8
votes
2answers
168 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
57 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
75 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
94 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
170 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
132 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
115 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 ...
0
votes
1answer
51 views

Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
2
votes
1answer
117 views

Optimal bounds for $k$-wise non-uniform random bits

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
3
votes
0answers
112 views

Dequantumizability known and unknown?

Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
0
votes
0answers
67 views

Where is the flaw in this proof that an LP solves TSP? [duplicate]

In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
2
votes
1answer
120 views

Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
2
votes
0answers
76 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
6
votes
1answer
180 views

Minimal generator for a set of sets

Is this a known problem? Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is ...
4
votes
0answers
128 views

Hereditary Substitution with Inductives and Eliminators?

I'm wondering, is there any existing work on hereditary substitution with inductive type families and dependent eliminators? In particular, normalizing the application of an eliminator to an ...
2
votes
1answer
96 views

Automata as term rewriting systems

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
5
votes
1answer
153 views

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...
6
votes
0answers
145 views

Immutable Space Model

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence? What is generally known about models of ...
3
votes
0answers
178 views

What is a good route for a math student to self study computer science systematically and efficiently?

I decided to ask this question after being attracted by how much one can do with the knowledge in computer science, including iOS application development, game(or mods) development, website creating, ...
-3
votes
1answer
77 views

Soundness of type (systems)

For someone without strong background in theoretical computer science: can soundness be a property of a type (given a type system), or a property of type systems only? In other words, can we say that ...
1
vote
0answers
40 views

Optimally fair stable matching

There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively. In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...
3
votes
1answer
389 views

Is there a counterexample to this work?

Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
1
vote
0answers
44 views

A categorized (?) list of functional pearls in JFP and ICFP

Is there a list of (categorized preferred) functional pearls ever published in ICFP and JFP? I could go to the ICFP proceedings and JFP issues and find all of them, but this would be time-consuming. ...
3
votes
0answers
56 views

Problems and theories in CS that uses Fibonacci numbers

I want to know problems and theories where Fibonacci sequence is used and where we have some possibility to use Fibonacci numbers. I have found that- In counting number of steps for Euclidean ...
10
votes
2answers
300 views

Hereditary substitution with a universe hierarchy

I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types. I'm wondering, are there any examples of hereditary substitution in ...
6
votes
1answer
174 views

Does Max Planar 3-SAT admit a PTAS?

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
2
votes
1answer
398 views

Possible to do Complexity theory with only counting and Pigeonhole

Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...