# Questions tagged [reference-request]

Questions requesting papers in the literature on specific, narrow issues.

962 questions
Filter by
Sorted by
Tagged with
18 views

### Generalization of finding $L_\infty$ centroid in $R^2$ via rotating and minimizing sum of $L_1$ distances

Given a set of points $x_1, \dots, x_n \in \mathbb{R}^2$, suppose one wants to find: $\text{argmin}_i \sum\limits_{j=1}^{n} \lVert x_i - x_j\rVert_\infty$ i.e. the point which minimizes the sum of the ...
34 views

### Books on Lambda calculus

I would like to learn Lambda calculus (informally). What are the pre requisites for studying lambda calculus ? Can someone recommend an interesting textbook that introduces subject historically with ...
21 views

### Is there a uniform way of giving for any mathematical formula a hypercomputer that computes it?

Some mathematical formulas directly suggest an algorithm for computing it (even if sometimes an inefficient one). For example, if we recursively define $\sum_{i=1}^nx_i=x_n+\sum_{i=1}^{n-1}x_i$, then ...
14 views

### Good exposition of tableau for first-order logic with equality?

I'm looking for a resource (online or printed) that explains in a self-contained way the classic tableau for first-order logic with equality. All I can find are expositions of tableaux for first-order ...
127 views

150 views

### Has category theory had an impact on computer science?

I've only learned bit of category theory, but so far its relation to type systems seems mostly descriptive. For example, you really don't need to know about coproducts to come up with the idea of ...
19 views

### Is there any research on allocating memory across multiple non-contiguous regions?

From my understanding, malloc and-the-like allocate contiguous blocks of memory. It then returns to you the start address of the memory block. This (and other ...
43 views

### Algorithms that must compute a global property?

Could you give me examples of polynomial-time algorithms that must compute a global property over their entire input? A purely illustrative example of this might be a graph algorithm that somehow must ...
61 views

### Longest Path Problem on Graphs of Bounded Clique-Width

The wikipedia article mentions: For graphs of bounded clique-width, the longest path can also be solved by a polynomial time dynamic programming algorithm. However there are no references and I wasn'...
84 views

### Distributed predicate computation on event stream

My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work. I'm working on a program that computes a predicate value (true or false) for ...
44 views

### Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
141 views

### Reference for counting the number of paths in a DAG

Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG . Is there a reference or name for the algorithm? ...
66 views

92 views

### Problems for which a small change in the statement causes a big change in time complexity

I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability. An example: The ...
14 views

### Misunderstanding of an NP-hard problem, $1||\Sigma w_jU_j$, that has polytime algorithm

The problem $1||\Sigma w_jU_j$ of minimizing the weighted number of tardy jobs in a single machine is NP-hard. This is well known and can be shown by reducing the knapsack problem to it. Also, when ...
28 views

### Examples for derandomization via small sample spaces

People in theoretical computer science stack exchange advises me to ask this question here. I ask the same problem in https://cstheory.stackexchange.com/questions/46668/examples-for-derandomization-...
39 views

### Problem with understanding Multi-party security circuit for secure stable matching

I am reading the following paper: MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation Paper Link I have following question: We have two groups shown in the circuit. Why we ...
16 views

### Parallel colouring to minimize collisions?

I have a graph in which there is a set of leader vertices $L$. There is no edge between any pair of leader vertices. Each leader vertex $u$ has a common set of colours $C$ and a set of neighbour ...
135 views

### Linear programming over a finite field

I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the ...
15 views

### Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as ...