1
vote
0answers
27 views

When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?

I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook. We are in the function-problem world. The problem ...
1
vote
0answers
26 views

Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model

What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model? In opposite direction what are implications ...
0
votes
0answers
22 views

Computing factorial using ring operations

Given $n,m\in\Bbb N$, is it known that computing $n!\bmod m$ with only ring operations needs $\Omega((\log n)^{1+\epsilon})$ ring operations where $\epsilon>0$?
1
vote
0answers
17 views

Convergence of online convex optimization methods

I am new to this subject so this question might seem a bit trivial Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
4
votes
0answers
46 views

Is `sort` typeable on elementary afine logic?

The following λ-term, here in normal form: ...
9
votes
3answers
542 views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" ...
1
vote
1answer
48 views

Maximum size-k cut

Here's my problem, Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and ...
1
vote
0answers
27 views

Are there any non-relativized separations between $L$ and $PH$?

In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
2
votes
1answer
31 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
8
votes
1answer
121 views

Randomized Polynomial Hierarchy?

I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$? It seems, we could still build a hierarchy, the same ...
1
vote
0answers
25 views

Favorable graph decomposition for dense graphs to solve independent set problem

I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or ...
1
vote
0answers
33 views

Number of $0/1$-monochromatic rectangles and communication complexity

What is the relation between number $0$-monochromatic rectangles in characteristic matrix and communication complexity? What is the relation between number $1$-monochromatic rectangles in ...
-1
votes
0answers
72 views

Can there be problems that cannot be derandomized?

Under some reasonable assumptions we know that $\mathsf{BPP\subsetneq NP}$ (no poly time randomized algorithm exists in $\mathsf{NP}$ complete situations). On other hand we believe that if a poly ...
5
votes
0answers
50 views

Minimum equivalent digraph with respect to sources and sinks

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$. Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that: For all pairs $u \in S, v \in T$ ...
-1
votes
0answers
20 views

understanding the definition of L-reduction of NPO problems

I read the definition of L-reduction in wiki https://en.wikipedia.org/wiki/L-reduction. I am trying to see if the following can be taken as definition of L-reduction. Also please suggest some books ...
11
votes
4answers
2k views

Math talk: Theorem about git revision control system?

I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry. For example, the HoTT (Homotopy Type ...
5
votes
2answers
155 views

Completeness under injective Karp reductions

Karp reduction is polynomial time computable many-one reduction between two computational problems. Many Karp reductions are actually one-one functions. This raises the question whether every Karp ...
8
votes
0answers
59 views

Chomsky-Schützenberger for Deterministic CFLs

Is there a Chomsky-Schützenberger representation theorem for deterministic CFLs? Knowing precisely the class of morphisms under which DCFL is closed, such a theorem would probably be of the form: ...
0
votes
0answers
35 views

Problem with the Inductive Types and recursors in LEAN

Reading the Lean online tutorial up to the section 6 "Inductive Types", I found a very confusing passage concerning the definition of the projection functions for the product type. Here is the ...
4
votes
0answers
33 views

Why do multi-stack visibly pushdown languages label each call/return with a particular stack?

In A Unifying Approach for Multistack Pushdown Automata, multistack visibly pushdown automata are defined in terms of an alphabet where each symbol is either a call or return for a particular stack or ...
2
votes
0answers
63 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
0
votes
0answers
70 views

Communication complexity problems with linear distance

Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions ...
6
votes
0answers
104 views

Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a ...
8
votes
1answer
78 views

Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
1
vote
1answer
124 views

What's wrong with this LEAN proof? [on hold]

I'm learning to use the LEAN theorem prover and I got stuck in a proof of a simple fact in first-order logic: $$ p(x) \rightarrow \forall x p(x) $$ My code is the following: variables (A : Type) ...
6
votes
1answer
191 views

An example where smallest normal lambda term is not fastest

Let the $size$ of $\lambda$-terms be defined as follows: $size(x) = 1$, $size(λx.t) = size(t) + 1$, $size(t s) = size(t) + size(s) + 1$. Let the complexity of a $\lambda$-term $t$ be defined as ...
-1
votes
1answer
27 views

Load factor of a hashtable: Why not resize based on number of actual buckets used? [closed]

From what I read, the load factor of a hashtable is defined as n/N where n=number of items N=Number of buckets in the hash table Its recommended you increase the size of your hashtable when load ...
7
votes
3answers
194 views

Would a proof assuming a physical law be considered sufficient?

I've always wondered if proofs in computer science would be considered sufficient proofs of the proposition if they needed to assume physical laws? For example, I'm wondering what would happen if ...
-3
votes
0answers
48 views

A cubic simple graph without cut edges is matching covered [on hold]

I recently found the following exercise: Given a cubic, simple undirect graph G without cut edges then G is matching covered, i.e. every edge is contained in a perfect matching. My idea was that, ...
0
votes
0answers
62 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
1
vote
1answer
65 views

Deterministic Parity Automata require unbounded index

Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become ...
-2
votes
0answers
60 views

Theoretical Computer Science Project Topic Suggestions [closed]

I am a Mathematics major about to go into my final Undergraduate year, which includes a one-semester project. I have a passion for Computer Science and I have learnt some programming languages (mainly ...
-4
votes
0answers
23 views

Recursive way to find all m-tuple from n-tuple [on hold]

Let $n>m$ be positive integers. I'd like to find all possible $n$-tuples $(a_1,a_2,\ldots, a_n)$, with $m$ of the $a_i$ equal to $1$, and the others equal to $0$. It seems to me that a simple ...
-1
votes
1answer
77 views

A sufficient condition for non existance of hamiltonian cycle

I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i ...
-2
votes
1answer
99 views

A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
0
votes
0answers
21 views

Analysis of a special case of Minimum Spanning Tree/Steiner Tree Ratio in graphs

Suppose we have a Minimum Steiner Tree $T$ in a graph $G=(V,E)$ on terminals $W\subset V$. It is well know that a Minimum Spanning Tree $\bar{T}$ on the metric closure $G_W$ of $W$ in $G$ gives $2(1 ...
3
votes
0answers
34 views

Finding string containing given collection of non-contiguous substrings and their multiplicity

Fix a finite alphabet. Given a collection $C=\{(s_1,m_1),\ldots,(s_k,m_k)\}$ of tuples of strings and integers. Is there an efficient algorithm to find all strings $s$ of a given length $L$ such that ...
13
votes
0answers
187 views
+100

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
-1
votes
0answers
27 views

How to modify 3-opt algorithm for ATSP

I have doubts about the implementation of the improvements that have been made to the TSP, so they can be adapted to the ATSP. Specifically the improvement is to use the list of candidates. Assuming ...
-4
votes
0answers
47 views

Bit operations in polynomial complexity

Supposing you have degree $N$ polynomials in $\Bbb Z[X]$. Using FFT techniques we can multiply both polynomials in $O(n\log n)$ multiplications. Now assume each coefficient is of size $m$ bits each. ...
-3
votes
1answer
95 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...
3
votes
2answers
141 views

Graph coloring/partitioning problem

I'm interested in the complexity of the following problem: Problem P: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{R}$ (so weights can be negative, too), color ...
13
votes
1answer
195 views

Permutations with forbidden subsequences

Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition. Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a ...
13
votes
4answers
214 views

Does the infinite graph of diagonals have an infinite component?

Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, ...
0
votes
1answer
70 views

“Checking equality for Kolmogorov complexity of two sequences” is computable?

It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not: "Given $x$ and $y$ as two sequences, ...
2
votes
0answers
30 views

Single-pass streaming quantile estimation using moments

Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f ...
4
votes
0answers
55 views

How much smaller can universal Turing machines get if they only need to be universal for a subclass?

Say that a Turing machine $U$ is universal for a class $\mathcal{C}$ of languages if for any language $L \in \mathcal{C}$, there is a word $w_L$ with: $$(\forall w)\quad w \in L \Leftrightarrow U(w_L, ...
4
votes
1answer
74 views

Concatenative binary lambda calculus/combinatory logic

John Tromp defines a version of the lambda calculus that is encoded in binary: https://tromp.github.io/cl/cl.html a) Does there exist a concatenative version of this language (or its combinatory ...
2
votes
0answers
27 views

Reference for randomized GMD decoding

The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a ...
4
votes
2answers
212 views

Constant in Komlos conjecture

Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some ...

15 30 50 per page