# All Questions

9,986 questions
20 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 ...
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 ...
29 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 ...
20 views

### comparing graphs representing source code

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

### 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 ...
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, ...
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 ...
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$...
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 ...
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 ...
59 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 ...
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 ...
56 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 ...
109 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 ...
31 views

### Is this in Chomsky Normal Form and why isn't a particular variable “useless”? [closed]

I think I've got it, but this is new and I'm having trouble understanding my professor. The original CFG: $S \rightarrow AAA | B$ $A \rightarrow aA | B$ $B \rightarrow \epsilon$ So this should ...
75 views

### What is the minimum number of bits required to encode $m$ numbers [on hold]

given $m$ numbers{$n_1$,$n_2$,...,$n_m$}, now we need to encode each number $n_i$ for those $m$ numbers, the requirement for the encoding method is as follows: (1) the result $E(n_i)$ for each ...
415 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 ...
19 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-...
70 views

### Is there a pseudorandom number generator that, given infinite memory, has no period?

I would like to have one or more examples of a PRNG that is computable by a Turing machine, has no period, and preferably is cryptographically secure.
25 views

### What is best approach to detect outliers?

I have a stream of numbers coming in and I want to flag them as 1 if outlier and 0 if not an outlier. I have two approaches for it: 1) I calculate rolling mean of numbers coming in. Then, I calculate ...
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 ...
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 ...
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,...
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 ...
240 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 ...
3k views

### Single author papers against my advisor's will?

I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor. My advisor is not involved in my research projects at all. In particular, ...
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 ...
93 views