0
votes
0answers
1 view

Proving The Riemann Hypothesis

The Riemann Hypothesis Theorem states that: There are infinitely many nontrivial zeros on the critical line and all these zeros have real part $\frac{1}{2}$. The proof is given by: $$\prod^\...
0
votes
0answers
9 views

Papers on using resource states to implement QFT efficiently

I recently came up with the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers ...
0
votes
1answer
23 views

Density of multiples

I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the ...
5
votes
1answer
282 views

How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?
-2
votes
0answers
56 views

Given a subset of vertices, find a cycle of a minimal number of edges that traverses all vertices in the subset

I am looking for an algorithm that given a connected, bridge-less, undirected graph and a subset of vertices, finds a cycle that traverses all the vertices in the given subset. However, I also need ...
-1
votes
0answers
29 views

Which papers state a mathematical formulation of a problem of building vehicle routes across an existing hub-and-spoke transportation network?

I'm developing a tool building (near-) optimal routes for an existing set of vehicles which serve a fixed hub-and-spoke network with two hubs. The goal is to minimise the total travel time of all ...
6
votes
2answers
100 views

Irreducible languages

This is not necessarily a research question. Just a question out of curiosity: I am trying to understand if one can define "irreducible" languages. As a first guess I call a language L "reducible" if ...
0
votes
0answers
51 views

The number of edges in the ith shortest path in a directed graph

$G$ - directed graph, $n$ - count of nodes According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges. Anybody can explain how this estimate is ...
-3
votes
0answers
46 views

Do we take these vertices? [on hold]

I am looking at an exercise about the vertex cover. We are given the undirected graph $G=(V,E)$ with $V=[10]$ and $E=\{(i, i+1)\mid i=1, \dots , 9\}$. Before I use the approximation algorithm, I ...
-3
votes
1answer
63 views

Could you explain to me the reduction? [on hold]

I am looking at the following solved exercise: I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why ...
4
votes
1answer
92 views

Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
-5
votes
0answers
37 views

What are some of the existing methods (preferably with implementations) that cluster dynamic brain network data with signed edge weights? [on hold]

0 down vote favorite I have a dynamic graph data with nodes and edges attributed to each timestep. The problem is to find how many communities are found at each timestep and what is their membership. ...
6
votes
0answers
70 views

Incomplete basis of combinators

This is inspired by this question. Let $\mathcal{C}$ be the collection of all combinators which only have two bound variables. Is $\mathcal{C}$ combinatorially complete? I believe the answer is ...
1
vote
1answer
80 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
2
votes
0answers
64 views

Computing Minima of the Projection of a Binary Cube

The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
4
votes
1answer
123 views

Is it possible to verify a typechecker for a total dependently-typed language in that language's logic?

I understand the diagonalization argument against implementing an eval function in a total language, and that typechecking in a dependently typed language requires ...
-1
votes
0answers
23 views

distance between codewords and preimages

Let $\varepsilon>0$. Does there exist a $[n,k,d]$ code over the field $\mathbf{F}_2$ that satisfies: $d(Cx,Cy)\in [\alpha(1-\varepsilon)d(x,y), \alpha(1+\varepsilon)d(x,y)]$ (where $C$ is the ...
1
vote
1answer
56 views

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said: The encoding disallows compression: it is not possible to work with encoding schemes that allow for ...
1
vote
0answers
17 views

Optimal evaluation of polynomials / rational functions

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
8
votes
0answers
101 views

Is the infinitely-often version of Ladner's theorem known?

We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other if and ...
-3
votes
0answers
101 views

What does $\tilde O(nm)$ mean?

I know that $\tilde O(n)$ means $O(n*(logn)^k)$ for some k. But what about when you have two parameters n, m? Would it mean $O(nm*(log(nm))^k)$ or $O(nm*(logn)^{k_1}*(logm)^{k_2})$ for some $k_1, k_2$?...
4
votes
0answers
47 views

Brute Force Search Algorithm for Semidefinite Programming (Representation of Spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
2
votes
0answers
23 views

Non-commutative quantum counting with aggregate constant work per increment

Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work: ...
-1
votes
0answers
24 views

Levelled Circuit vs. Layered Circuit

For a boolean/arithmetic circuit, is layered the same as levelled except layered must have the same type of gate in each level?
-1
votes
0answers
32 views

definition of ε-net theorems [on hold]

I'm a graduated computer science student and now working on epsilons net and the other computational geometry subjects related to this. In many references and articles some good things have done. ( ...
-3
votes
0answers
52 views

DFA for a binary number divisible by 3, 5,7 [on hold]

Is there a generalized procedure to construct the DFA to find if a binary string is divisible by 3 or 5 or any odd number. Like using transition table to design the DFA rather than directly working ...
0
votes
1answer
114 views

Realation between Group theory and Information theory

Motivation: I am interested about the application of group theory in Information theory. To be precise, I am interested in Data Compression (Source Coding Theory). Question: Is there any paper/survey ...
6
votes
1answer
88 views

Chomsky Schützenberger enumeration theorem

In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some ...
3
votes
1answer
54 views

Quick Sampling from Probability Distribution: Is there a name for this algorithm?

I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm. Givens: $N,$ the number of elements to ...
-2
votes
1answer
64 views

Given oracle for Max-3SAT compute clauses that cannot be satisfied

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
0
votes
1answer
93 views

Online/approximate weighted and capacitated bipartite matching

I wish to take a look at online/approximate weighted and capacitated bipartite matching problem. Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
5
votes
4answers
174 views

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge ...
3
votes
0answers
86 views

Problems in NC not known to lie in NC2

Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
7
votes
1answer
106 views

Ordering of a DAG minimizing some definition of cost

Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i \mid \exists k>i: (v_j,v_k)\in A\...
-1
votes
0answers
59 views

Explicit Computational Complexity of the Shortest Weight Constrained Path Problem?

The Shortest Weight Constrained Path Problem is a known NP-Complete Problem (listed NPC in Garey and Johnson - ND30]. Thus, by definition the running time of the Problem is exponential in the worst ...
-1
votes
0answers
45 views

Does there exist any distributed algorithms for the Minimum Feedback Arc Set Problem

I am wondering if there are any known distributed algorithms for the Minimum Feedback Arc Set Problem. Exact solutions, approximation algorithms, and heuristic approaches all welcome.
8
votes
2answers
167 views

Can the “mutual independence” condition in the Lovász local lemma be weakened?

The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows. Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is ...
-6
votes
1answer
60 views
+50

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
2
votes
1answer
117 views

Damas-Milner-like subset of the calculus of constructions with global type inference

Damas-Milner is a subset of System Fω that gives up expressivity (type-level computation) for usability (type inference). The experience with Haskell and ML attests to the practical value of this ...
-3
votes
1answer
49 views

Addition on a quantum computer

From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers. For a simple arithmetic operation such as a+b+c+d where ...
10
votes
2answers
103 views

Collapses under the assumption that $NEXP\subseteq P/Poly$

It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$. What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?
9
votes
2answers
451 views

What are some interesting applications of homotopical algebra in theoretical computer science?

I am an homotopy theorist, interested in computer science. I would like to ask what are some interesting applications of homotopical algebra (model categories, infinity categories, simplicial ...
5
votes
1answer
84 views

Asymptotic complexity of CDCL SAT solver that only selects negative literals

If a CDCL SAT solver only selects negative literals as decision literals (but can set positive literals through unit propogation) but has a perfect heuristic for determining which literal to select ...
1
vote
1answer
96 views

Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. ...
0
votes
0answers
40 views

Are there any heuristics that works solely on graphs?

I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work ...
-2
votes
0answers
23 views

How can I understand better the Libra method for arrays?

The Libra method as I learned can help with finding the smallest sum in an array. When given an array, you use two pointers : One to the first index and one to the last index.And each iteration you ...
0
votes
1answer
28 views

The logic in derivation of virtual welfare

I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment ...
-5
votes
0answers
35 views

Why there is no quantum walks on hypergraph?

As a beginner,I find that there is no quantum walks on hypergraph.why?
4
votes
0answers
46 views

A question on the introduction of the Wagner hierarchy from K. Wagner's original paper

My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets. In ...
-2
votes
0answers
90 views

What are the known models of computation? [closed]

We have the following models of computation: ...

15 30 50 per page