All Questions

9,928 questions
14 views

Is P-complete self-reducible?

By Self-reducibility, we understand that a search problem can be reduced to the self problem but by a decision problem instead of a function problem. P is trivially self-reducible, but what about P-...
6 views

No cyclical variable references within a for-loop = enough?

Suppose you had a machine programming language which has: Integer variables in some field $\Bbb{Z}_n$, though for small magnitude integers, this behaves completely like we're "in the integers". ...
29 views

Why are all finite languages regular? [on hold]

It is said that "All finite languages are regular". But the Pumping Lemma says that, if a language is regular one can find a 'large-enough' word w such that it can be decomposed into w = xyz such ...
23 views

Counting class for DP problems

What would be the corresponding counting complexity class for decision problems in $DP$? Recall that $DP:=\{\mathcal{L}_1\cap\mathcal{L}_2\mid \mathcal{L}_1\in\text{NP},\mathcal{L}_2\in\text{coNP}\}$ (...
55 views

What are CS blogs for puzzles/games?

I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?,...
42 views

On derandomizing $BPP$ problem

It is believed derandomizing $BPP$ to $P$ involves good PRGs and faces lower bound barriers. Does derandomizing to $P^{NP}$ face similar issue or is there evidence that it is vastly easier?
26 views

84 views

Definitional equality of recursive function definition by “infinite unfolding”

The context is checking definitional equality in dependent type theory implementations. Consider in Coq ...
60 views

Is there any problem that cannot be solved in O(n!) time? [closed]

In other words, does a problem exist such that if we try to compute a solution it, then it's running time grows faster than n! (factorial of n)? If it does exist, give me some examples and if it doesn'...
16 views

69 views

Computational hardness for sampling a uniform matching

A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
57 views

Proof that CIC or Dybjer-style eliminators are strongly-normalizing?

Related to this question I'm wondering, what is the standard technique for showing that dependent types with eliminators are strongly normalizing? I'm thinking something like the Calculus of ...
146 views

P and Descriptive Complexity

In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. However, ...
90 views

Parallel building time of a k-d tree on n points with n processors

Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree? A straight forward parallelization would be as ...
$k$th element in data stream
In the streaming model how can i find the $k$th element (not $k$th most frequent) with erorr of at most $\pm \epsilon$ s.t. we return index $i$ that $(1-\epsilon)k \leq i \leq (1+\epsilon)k$ using ...