# All Questions

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

### Is sort typeable on elementary afine logic?

The following λ-term, here in normal form: ...
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" ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
21 views

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, ...
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 ...
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 ...