# All Questions

10,094 questions
63 views

### Uniqueness of the distribution maximizing the channel capacity

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
144 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 ...
28 views

### Scheduling with Separation Constraint

There are $N$ types of jobs. For each $i$, we have to schedule $T/D_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum_{i=1}^N 1/(D_i+1) = 1$. For each type $i$, the distance between two ...
179 views

### Determining how n-tuples are sorted as you search them?

I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, ...
50 views

153 views

### $\exists \mathbb R$ and IP

We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP? What about the other direction, are there some Arthur-Merlin ...
189 views

### Turing Machines as Coalgebras

I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
28 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 ...
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 ...
72 views

### Minimum cut with nonlinear objective function

Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum. Let us generalize it the following way: let $f$ be a ...
149 views

### Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
53 views

### Which research fields deal with this variant definition of Boolean circuit depth?

Disclaimer: I admit that the question is not very clear. I think it cannot be helped because the question is very open-ended. First of all, I present the interested type of circuits. We only consider ...
77 views

### Densest k subgraph problem for outerplanar graphs?

The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$. Does anyone know if there exists a polynomial-time ...
69 views

### Machine Learning Algorithm To Fill Data Holes

I'm having trouble finding a good place to begin with this. I'm just looking for a name or point to start researching a Let's say I have 1000 records. 10 of these records are only 90% complete. The ...
82 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$...
76 views

### Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
151 views

### Is there a notion of “inevitable reduction?”

I was just working on a semantics paper and realized I needed a notion of inevitable reduction. I came up with this definition: Let $\rightarrow$ be a binary relation. We say that $a$ inevitably ...
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 ...
133 views

### NP-hardness proof of selecting the ''fittest'' topological sequence of a DAG

Given a directed acyclic graph (DAG) with $n$ vertexes $V=\{v_1, v_2,...,v_n\}$ and a given permutation of those $n$ vertexes $P=[p_1, p_2,..., p_n]$ that $\forall i, p_i\in V$. Note that $P$ could ...
506 views

### What is the “question” that programming language theory is trying to answer?

I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which ...
21 views

### Does optimal fitting flat must pass through the mean of the point set?

I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line. Project clustering is a natural generalization of k-...
79 views

### Are both safety and liveness properties closed under finite intersection?

Given two safety properties $P_1$ and $P_2$, is their intersection $P_1 \cap P_2$ also a safety property? Similarly, if $P_1$ and $P_2$ are liveness properties, is $P_1 \cap P_2$ also a liveness ...
165 views

### In light of Raz and Tal's results, what can we say about whether there's a BQP problem for each level of the polynomial hierarchy?

[cross-posted on QCSE a couple of weeks ago] Every Venn diagram or Hasse diagram I see illustrating the "standard model" of computational complexity describes a universe of $\mathsf{PSPACE}$ problems,...
92 views

### What can be some bachelor thesis ideas in Quantum random walks?

Note: Cross-posted on Quantum Computing Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
159 views

### String theory based computations

I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
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 ...