# All Questions

9,986 questions
34 views

### Is there a pseudorandom NP complete problem? [on hold]

The subject line pretty much says it. Is there an NP complete problem which is pseudorandom? The exact notion of pseudorandomness I want to leave open to different possibilities, but I have in mind ...
22 views

### Determine the error-probability of biased coin tosses using chernoff-bounds

Let's assume we have a biased coin with probabilities $\frac{4}{5}$ and $\frac{1}{5}$ and we don't know to which event (head or tail) the probabilities belong to. But we want to decide it by majority ...
106 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 ...
40 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 ...
59 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 ...
70 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)?
37 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 ...
13 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 ...
1k views

### Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also talk at University of Illinois, Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2,...
20 views

### comparing graphs representing source code

I have a graph (tree) that represents the code structure. For example for this simple code ...
241 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 ...
26 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 ...
28 views

### Wave propagation (with application specific parameters) in a graph of nodes

In a graph of nodes, all nodes are connected to n other nodes. Periodically a random node emits a pulse, that propagates from node to node, and decreases in strength with k steps from pulse emitter as ...
39 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 ...
59 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 ...
133 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 ...
48 views

### Is the aforementioned puzzle NP-hard or NP-easy? [on hold]

I've created a game based on Sudoku. The same general rules apply. All, I want to know is if the puzzle is considered NP-complete just like other puzzles. Considering that Numberlink is NP-complete, ...
380 views

### What kind of reinforcement learning is MENACE?

The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description: ...an interesting machine ...
66 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$...
58 views

### Why can we (apparently) implement CFG parsers only using (N)DFAs?

I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested. For parsing those files I ...
13 views

### Need help in figuring out how an LALR parser is parsing a given input for my grammar

Im using the PLY python package to build a front-end compiler for a subset of C, but Im still struggling to understand how the bottom up parser(specifically LALR) works. I wrote a simple program with ...
442 views

17 views

### Lateral gene transfer and the origins of Life and how can that be analyzed from a mathmatical perspective [closed]

Albeit the complexity of protein folding is most certainly a difficult problem to pose to a computer as I would expect....there are an ALMOST infinite number of folds I would imagine. Here is my ...
42 views

### I was wondering about which mean I should use? The geometric mean or the arithmetic mean [closed]

I have an optimization problem (minimization problem) and the table (below) represents a comparative study between the results of two methods, the first one performed better than the second one and to ...
135 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,...
71 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 ...
64 views

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

I am an undergraduate, reading Quantum information and quantum technology. For about some time, I am interested in applications of Quantum walks to quantum algorithms. Can anybody suggest a start ...
58 views

### Theoretical difference between OS and Compiler [closed]

What is the theoretical difference between an OS and a compiler, besides that one exists and run time and the other mostly exists at compile time? By OS I'm referring to the kernel and higher levels. ...
126 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 ...
136 views

### Largest “non-disturbing” subset in a graph

The definition: The subset of vertices in a graph is called "non-disturbing" if any two vertices from this subset could be connected by a path not passing through other vertices of this subset. ...
451 views

### Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does ...
118 views

30 views

### minimizing monotone submodular function with cardinality constraints without non negativeness

I am looking for approximation algorithms for minimization of monotone submodular functions with cardinality constraints. But my set function is not nonnegative. As far I know, most of the algorithms ...
48 views

### Tradeoff between running time and depth in neural network

I might not be in the good stack-exchange site, so please forgive me. Let consider a neural network that we want to train to a certain task. For the purpose of my research, I am wiling to reduce the ...
98 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$...
According to Moggi's 1991 paper "Notions of computation and monads" one can represent monadic equational logic with the well known monad $(T, \eta, \mu)$ with T an functor and the two natural ...