All Questions

-2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-2
votes
0answers
20 views

comparing graphs representing source code

I have a graph (tree) that represents the code structure. For example for this simple code ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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)?
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
-4
votes
0answers
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, ...
-1
votes
2answers
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 ...
3
votes
0answers
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$...
-1
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
2
votes
0answers
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 ...
5
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
10
votes
1answer
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 ...
0
votes
0answers
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-...
-1
votes
0answers
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.
-2
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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,...
3
votes
0answers
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 ...
-1
votes
0answers
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. ...
3
votes
1answer
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 ...
10
votes
1answer
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 ...
32
votes
4answers
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, ...
-2
votes
0answers
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 ...
2
votes
1answer
93 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
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$...
0
votes
0answers
27 views

“Noisy channel” vs. “unreliable channel”

If someone uses the term "noisy channel", and another person uses the term "unreliable channel", do they mean the same thing? If these are different things, or if they are the same things but one is ...
-1
votes
0answers
27 views

Proving a statement is equivalent to another

I'm reading Semantics with Applications and I've stumbled upon a question I don't quite understand. It's about proving two statements are equivalent to each other. At the very end, I don't understand ...
6
votes
2answers
491 views

What logic correponds via Curry-Howard to a Monad?

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 ...
1
vote
0answers
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 ...
5
votes
1answer
118 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
49 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
37 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 \...
2
votes
1answer
47 views

Can Isorecursive types capture mutually recursive data types?

I've been reading TAPL, and reached the section on recursive types. I understand the type operator $\mu$. For example, the two type expressions are equivalent ...
6
votes
0answers
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. ...
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 ...
-1
votes
0answers
38 views

algorithm to find small diameter acyclic orientation of a vertice-weighted graph

I am searching for an practical algorithm to find an acyclic orientation of a vertices-weighted graph which has a diameter as close as possible from the smallest diameter of those acyclic orientations....
4
votes
2answers
156 views

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including ...

15 30 50 per page