# All Questions

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^\...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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\}$-...
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 ...
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 ...
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 ...
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 ...
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 ...
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$?...
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 ...
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: ...
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?
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. ( ...
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 ...
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 ...
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 ...
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 ...
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 ...
93 views

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 ...
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.
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 ...
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 ...
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 ...
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 ...
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$?
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
35 views

### Why there is no quantum walks on hypergraph?

As a beginner,I find that there is no quantum walks on hypergraph.why?
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 ...