Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
31 views

Uniform convergence for a class of finite dimension

The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. ...
2
votes
1answer
215 views

How to translate automatons (Turing machines) into programs of high level programming language?

Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the ...
0
votes
0answers
14 views

Companion volume to Concurrency verification of Willem-Paul de Roever

At the moment I am working hard with the book "Concurrency Verification Introduction to Compositional and Non-compositional Methods" written by Willem-Paul de Roever et al. In the ...
0
votes
0answers
4 views

Inferring reward function and transition model from optimal policy

Consider an MDP where the transition model and the reward function are unknown. Consider an optimal policy $\pi^*$ generated from this MDP (say by some oracle who does know the transition model and ...
4
votes
1answer
95 views

Is there a graph theory textbook that covers treewidth thoroughly?

Can someone recommend a graph theory textbook that covers treewidth thoroughly? Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them....
1
vote
0answers
10 views

Asking for references on errors, testing, system failures etc

I am looking for references that talk about the following subject: Software programs are in general complex systems. That is, if we decompose them into components and we make sure that each component ...
1
vote
1answer
91 views

Where were the ideas of vote, accept and commit phases originally introduced?

In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5. Is this a novel introduction or has this been previously been ...
2
votes
1answer
118 views

Do white box methods for feature extraction exist for facial recognition?

Part of something I'm working on (or rather begin working on) involves white box approaches to facial recognition. I previously worked on something for character recognition using scene segmentation ...
1
vote
1answer
26 views

Algorithmic information theory with stochastic algorithms?

Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, ...
1
vote
0answers
14 views

Degree of regularity of a Markov chain

A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive. Is there a known notion of degree of regularity quantified in terms of how soon all ...
4
votes
1answer
237 views

What was Robert Floyd's algorithm for inserting brackets?

In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
1
vote
0answers
28 views

Reliability of information on large social networks like Wikipedia [closed]

I was going through the playlist of an online course on Social Network Analysis offered by the Indian Institute of Technology (Madras), when I came across the claim that "when a lot of people get ...
2
votes
1answer
37 views

What is a self-delimiting program?

I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974. Unfortunately ...
13
votes
3answers
4k views

What is the origin of the client server model?

I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
2
votes
0answers
17 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 ...
0
votes
0answers
23 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 ...
0
votes
0answers
16 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 ...
1
vote
0answers
12 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 ...
6
votes
1answer
97 views

Minimum set cover with incompatible sets

I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously). To state it more formally: We have a finite base set $X$ and a family $\...
7
votes
2answers
677 views

Are there any implementations of the spineless tagless G-machine other than in GHC?

From Simon Peyton Jones (recent Royal Society member) we read the paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine. Now this paper is part of how they ...
0
votes
0answers
19 views

Reference request: Learning runtime analysis (Complete material)

I am very curious about learning runtime analysis more than just what MIT courseware provides (The course with Erik Demaine 6.006) And what CLRS offers, which is a nice explanation about asymptotic ...
13
votes
6answers
46k views

Definition of the state of an object in OOP

I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find ...
5
votes
2answers
2k views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
2
votes
1answer
49 views

Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
0
votes
1answer
33 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 ...
0
votes
0answers
15 views

What the the most efficient and effective VM ISA/computational model format backed by research?

The JVM and CLR are stack based machine are very efficient, mainly due to the investment in these platforms than an efficiency and effectiveness of stack based VMs. For en entity that does not have ...
7
votes
3answers
981 views

Simple proof for NP-completeness of Edge Dominating Set

In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to ...
1
vote
0answers
23 views

Cloud computing application [closed]

Question I want to analyze the potential of a cloud computing application that performs payroll and invoicing over the Internet from a large Internet company.I want also to describe the systems ...
0
votes
0answers
18 views

Extending the token bucket algorithm

I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies....
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
1
vote
1answer
42 views

What is a task type?

I have an unlabeled dataset: 500 X-rays of seeds in husk. In each image there are different number of seeds, for instance, from $10$ to $50$. A seed has some features. The main features are a seeds' ...
3
votes
0answers
59 views

bounding the height of stack when checking acceptance pushdown automaton

Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form. There exists a constant $c$, computable from $A$, such that: if $w$...
1
vote
1answer
21 views

linear time nash equilibirum aproximations for two player zero sum games

I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
0
votes
1answer
29 views

Reference asking : High Performance Computer Architecture

Topics Pipelining: Basic concepts, instruction and arithmetic pipeline, data hazards, control hazards, and structural hazards, techniques for handling hazards. Exception handling. Pipeline ...
0
votes
0answers
17 views

Modern vs. original formulations of Rice's theorem

Rice's theorem states that any nontrivial semantic property of Turing machines is undecidable. However, when I opened “Classes of recursively enumerable sets and their decision problems” by H. G. Rice,...
1
vote
0answers
18 views

“Close” Graph Coloring?

I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive ...
1
vote
1answer
86 views

Is SEMIPRIME in P?

The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
7
votes
1answer
209 views

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph [closed]

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
0
votes
0answers
23 views

Distributed Serializable Snapshot Isolation

I was wondering if there is any research on distributed transaction algorithms for Serializable Snapshot Isolation. I found Binnig, C. et al.: Distributed snapshot isolation: global transactions pay ...
1
vote
1answer
32 views

Given a list of integer rectangle areas, find all integer rectangles that they can tile

Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings? Every integer rectangle area in the list (multiset) must be ...
2
votes
2answers
75 views

Is realization of unit disk graphs hard?

It is known that recognizing a unit disk graph is NP-hard [1]. However, the paper does not mention how hard the realization problem is. I have looked up several references [2][3][4]. None of the ...
9
votes
3answers
4k views

Deleting in Bloom Filters

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
0
votes
0answers
19 views

Textbooks about the verification of computer programs that use Z as the specification language

I'm looking for textbooks/lecture notes about the verification of computer programs, i.e. proving their correctness, that use Z as the specification language against which the correctness is verified.
1
vote
1answer
24 views

What is a good reference for NP hardness in the machine learning/optimization/operations research context?

I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example: Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
0
votes
1answer
43 views

Bottleneck TSP with repeated nodes

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
0
votes
2answers
71 views

How to tell if a grammar is LALR(1) formally?

There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations ...
2
votes
1answer
46 views

A voting scheme where votes are scriptable

I am looking for literature on mathematical models of (political) voting schemes. Concretely, I am interested in models that allow votes of the following form: "I am voting for $X$, but only if $...
1
vote
2answers
106 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 ...
1
vote
0answers
16 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 ...
0
votes
1answer
41 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 ...

1
2 3 4 5
19