# All Questions

11,629 questions
Filter by
Sorted by
Tagged with
8 views

### Can equations be used to transmit large amounts of information instead of directly sending it?

Can equations be used to send large amounts of information rather than sending the information itself you send an equation that when solved reveals the information? So rather than downloading billions ...
28 views

40 views

### Expert Opinion on the Importance of Polynomial Hierarchy Collapse

$P\ vs\ NP$ and $NP\ vs\ co-NP$ are perhaps the two central questions in TCS and Complexity Theory with numerous surveys devoted to these problems. But (relatively) not much has been discussed ...
29 views

### Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
19 views

41 views

### Equivalence of XML queries

$\textbf{Problem statement:}$ Given a set of tree patterns $\{P,P_1,...,P_k\}$ where each $P_i$ has the same topology as $P$ (i.e. $P_i$ and $P$ have the same sets of nodes and edges excepting the ...
32 views

### Using error-correcting codes in multi-player games

There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
165 views

### The Riemann Hypothesis as an halting problem

Matiyasevich has reformulated RH as a computer science problem : "a particular explicitly presented register machine with 29 registers and 130 instructions never halts", see this reference . ...
758 views

### Randomized algorithms not based on Schwartz-Zippel

Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
804 views

49 views

### Computational complexity of factoring univariate polynomials with positive integer coefficients

I am interested in the computational complexity of the following problem. Input: a polynomial p(x) with positive integer coefficients Output: a factorization of p(x) into irreducible factors having ...
104 views

### improved analysis of spectral gap of zigzag product?

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction: Moreover, the variational ...
59 views

A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \... 0answers 41 views ### Properties of half-way locally bijective homomorphisms between Eulerian orientations Short Version Let$G$and$H$be two Eulerian graphs and let$\overrightarrow{G}$and$\overrightarrow{H}$be Eulerian orientations of those graphs. Let$f$be a homomorphism from$G$to$H\$. (...

15 30 50 per page