# All Questions

9,928 questions
4 views

### Extending EAL with recursion makes it incompatible with the abstract algorithm?

A few years ago, I've asked if Elementary Affine Logic can be used as the core type system of a practical programming language. The accepted answer argues that, yes, although such language would be ...
53 views

### Can be converted UNAE3SAT into a P-complete decision problem?

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-...
42 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 ...
26 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}\}$ (...
90 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?,...
49 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

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