# All Questions

12,695 questions
Filter by
Sorted by
Tagged with
137 views

### On perm+1 and det+1

Given a balanced bipartite graph G and a planar graph H. We do not know the number of perfect matchings in G and we do not know the number of spanning trees in H. But assume they are at least 3 both. ...
46 views

### Deamortization of basic COLA (Cache oblivious lookahead array)

I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA. The paper says that for every level k, for deamortization, ...
31 views

3k views

### What are examples of recent relatively simple 'toolbox algorithms'?

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such ...
42 views

### Effective algorithms for finite lattices of (higher-order) monotonous functions?

I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
121 views

### What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines. What is the reference for non-deterministic ...
1 vote
96 views

### Do realizable systems always have some non-well-founded sets?

Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following: LEM is not realized (e.g. this MSE answer) The traditional ...
342 views

78 views

### Status of QNC vs. PSPACE

It is known that $\text{NC} \neq \text{PSPACE}$, now I am wondering if there is a similar separation for $\text{QNC}$, the class of decision problems solvable by polylogarithmic-depth quantum circuits ...
187 views

### Can you regain the Church-Rosser property in languages with continuations?

I'm aware that if you naively add continuations to a language, the Church-Rosser property no longer holds. For example, suppose we have some variant of the STLC with basic arithmetic and integer types....
610 views

### NP-complete problems where the inputs are prime numbers

Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
154 views

67 views

### What's the exact complexity of a DFS if we revisit nodes?

By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
74 views

### Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$

I am able to solve this using brute force but curious if there is a better approach. Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
20 views

### The minimal number of messages required to solve the mutual exclusion problem in a symmetric distributed system

In the seminal paper introducing their namesake algorithm for solving the mutual exclusion problem in a distributed system, Ricart and Agrawala assert (in the first paragraph of section 4 Message ...
124 views

### Locally nameless representation implementation

ORIGINAL: I am programming a functional compiler and found out about locally nameless representation (using de brujin indeces for bound variables and names for free variables). I just don't understand ...
102 views

### clique problem in graphs with bounded degree

Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
103 views

### Implicit characterization of sublogarithmic space

Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine ...
665 views

### What is a very simple pseudodeterministic algorithm (for educational purposes)?

Definition. A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability. Question. The notion of a ...
35 views

### Using an offline approximation algorithm within an online algorithm

When defining an online algorithm, it is common to assume that there exists an optimal offline algorithm to be used over the set of already known requests. For example, consider the IGNORE algorithm ...
65 views

### Construction of a PDA for the binary and decimal representation of a number

I have the solution with me for this question but I have really hard time understanding the construction. Can anyone may be break it down in a simpler way? Problem: Given $n \in \mathbb{N}^+$. ...