# Questions tagged [reference-request]

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

1,041 questions
Filter by
Sorted by
Tagged with
22 views

### How does the BIOS teletype routine work?

I am writing an OS. I am not a computer scientist, I am a physicist, so my understanding of computing is limited enough that I don't yet know how to ask the right questions. I am looking for either a ...
• 1
13 views

### Looking for references that can teach me some of the fundamentals of computer science (from Peter Norvig's TYPITY page)

I am looking for resources/books/blogs etc from which it can tell me "how long it takes your computer to execute an instruction, fetch a word from memory (with and without a cache miss), read ...
• 11
47 views

1 vote
23 views

### CNF Horn-renamability to 3-CNF Horn-renamability reduction?

A CNF formula is Horn-renamable if you can invert variables in such a way that each clause has at most one positive literal. There is an algorithm based on a reduction to 2-SAT given in Renaming a Set ...
• 1,901
64 views

### NP-hardness of partitioning into k sets

Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum? For $k = 2$, this is the well-known Partition problem. For general $k$,...
1 vote
36 views

### Seeking a reference for NP-hardness of optimization problems

Most optimization textbooks do not cover the concept of NP-hardness. Some examples include: "Convex optimization" by Boyd and Vandenberghe "Numerical Optimization" by Nocedal and ...
• 821
25 views

### Name of graph family defined by modular sum

In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges ...
• 861
207 views

### How to Prepare for Informatics Olympiad and ACM-ICPC?

As a beginner to competitive programming, I want to know a few things about informatics Olympiad such as the resources and books needed to prepare for the competition. I also want to know which ...
• 111
41 views

### Prior or subsequent art for Microsoft COM’s “causality IDs”

Microsoft COM, in its object RPC part, had a peculiar mechanism that could be used to prohibit concurrent calls to the same object (or another object serviced by the same event loop) but permit ...
24 views

### Current best output-sensitive algorithm for computing all maximal cliques of a graph

I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph. I know the Bron-Kerbosch algorithm is highly utilized, but ...
1 vote
38 views

### Toda's theorem without $\oplus P$

Toda's theorem says that the polynomial time hierarchy is contained in $P^{\#P}$, the class of problems solvable by polynomial time oracle Turing machines with access to an oracle in #P, which is the ...
• 433
1 vote
35 views

### Articles and journals for undergrad students

I am searching for a CS equivalent to American Math Monthly. It should contain articles on topics and some problems at the end for submission. I need some recommendations . Thanks in advance.
• 31
70 views

### Is there any computation formalism based on general relativity?

Quantum mechanical principles have already been used to attack computer science problems in the form of quantum computing. In a similar vein, is there any usage of general relativity principles to ...
75 views

### Division of Large Numbers with Known Factors

Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$. Required is their ...
25 views

1 vote
21 views

### Reference request for book on design patterns with foreword by Christopher Alexander

I do recall having found a book on software design patterns with a foreword by Christopher Alexander. Now, as is well known Alexander is credited as the creator of the concept of design patterns and ...
1 vote