Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
6
votes
2answers
127 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 $\...
0
votes
0answers
22 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 ...
2
votes
1answer
59 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
0answers
19 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 ...
1
vote
0answers
26 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
23 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, ...
4
votes
1answer
100 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
1answer
44 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' ...
0
votes
1answer
47 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 ...
1
vote
1answer
24 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. ...
3
votes
0answers
63 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
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
50 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 ...
1
vote
1answer
28 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
57 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 ...
1
vote
2answers
226 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
50 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
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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'...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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? ...
2
votes
1answer
66 views

Context free languages invariant by "shuffling" right hand side

Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.: $A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; ...
5
votes
1answer
80 views

Factoring algorithms after number field sieves

It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. ...
2
votes
0answers
49 views

Complexity of approximating a function value using queries

I am looking for information on problems of the following kind. There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
2
votes
2answers
81 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 ...
5
votes
1answer
74 views

Does big-Oh impose an ordered partition on the set of the "usual" functions?

The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not ...
3
votes
1answer
211 views

Functional Programming and Category Theory

I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked ...
4
votes
1answer
75 views

Algoritm to sample an even subgraph of a graph

In some problems related to the Ising model in physics and mathematics the following problem comes up: Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep ...
3
votes
2answers
82 views

Books for the Mathematical Theory of AI/ML

I am interested in the mathematical foundations of Artificial Intelligence and Machine Learning. Are there any books which will describe and present the mathematical foundations in detail? I am not ...
4
votes
0answers
39 views

What are some advanced background topics I'll need for distributed systems and networks research?

I am a new graduate student in Computer Science who would like to be able to read and understand modern and new distributed systems research papers. My current background / courses and understanding ...
1
vote
0answers
177 views

Advanced Master Theorem?

I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I ...
3
votes
1answer
47 views

Reference asking: phase transition in SAT

This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate. It has been experimentally observed (e.g. here) that when ...
2
votes
1answer
33 views

Partitioning tuples

Given are tuples $(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $i=1,\...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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-...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
142 views

Data Compression :Compress a Compressed File

Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
4
votes
0answers
65 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...

1
2
3 4 5
20