Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
900
questions
1
vote
2answers
57 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
10 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
38 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 ...
3
votes
0answers
49 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
81 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 ...
0
votes
0answers
20 views
Books on scientific computing, efficent NN inference, and matrix multipication
I'm trying to learn more about how inference, matrix multiplication, and scientific computing (primarily with tensors/matrices). I'm not sure what the classics here are or what good sources are. I'm ...
0
votes
0answers
21 views
Strategies for event-driven concurrency
Is there any good formal investigation or at least definition of different strategies of event-driven concurrent programming?
I've read that there exist readiness based (pull based) and completion ...
2
votes
1answer
42 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 ...
0
votes
1answer
41 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
26 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
63 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
44 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
0answers
33 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 is the realization problem.
I have looked up several references [2][3][4]. None of the ...
5
votes
1answer
56 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
101 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
51 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 ...
2
votes
2answers
58 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
30 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
40 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
32 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
21 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,\...
0
votes
0answers
17 views
Reference on PCP theorem
Can someone recommend a reference on the PCP theorem that explains how it works via examples rather than formal CS language?
Specifically, I'm looking for the example on how graph colouring can be ...
2
votes
1answer
62 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 ...
0
votes
0answers
16 views
Proof of Hungarian Algorithm Matrix Formulation
Can someone explain or give a reference as to how the Hungarian Algorithm in its matrix formulation always gives a correct answer? I've seen proofs of correctness of the bipartite matching formulation,...
1
vote
0answers
12 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
23 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
31 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
13 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
55 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
13 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
64 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
53 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
vote
0answers
56 views
Fastest way to find a substring 'ab' inside a string 'abab'
Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters.
The alphabet I am interested in is the set of all ordinary letters ...
0
votes
0answers
25 views
Lambda calculus self reducer with explicit redex selection
In "Efficient Self-Interpretation in Lambda Calculus", Mogensen presents a self-reducer in lambda calculus which leaves redex selection to the underlying reduction.
Is there some example of a self-...
1
vote
2answers
68 views
resource on translating imperative programs to functional programs
I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional ...
1
vote
0answers
17 views
Self reduction for fully introspective lambda calculus representations
For some representation scheme $\ulcorner \cdot \urcorner$, a self interpreter $R$ is a lambda expression where $R \ulcorner A \urcorner \underset{\beta}{=} A$, while a self reducer $E$ is a lambda ...
5
votes
1answer
76 views
Good book on the history of programming languages?
I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, ...
0
votes
0answers
20 views
Textbook on how processors are actually structured at the circuit level
I am looking for a textbook that helps me understand how basic digital electronic units are used to build complicated integrated circuits.
I have looked online for textbooks, but what I have found ...
1
vote
0answers
36 views
Diameter of a random graph
I'm considering the standard Erdös/Renyi $G(n,p)$ model where we have $n$ nodes and each possible edge is sampled independently with probability $p = \frac{1}{n^\epsilon}$.
It is relatively ...
2
votes
1answer
41 views
Finding C-convex holes in a planar point set
I am looking for an efficient algorithm to find convex holes in a given point set.
The problem is
Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
1
vote
1answer
45 views
trace vs. computation vs. run vs. execution vs. walk
Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions. Does any work distinguish between these ...
6
votes
0answers
104 views
Time complexity of linear programming with small number of variables
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
0
votes
0answers
21 views
In what sense the computer program (Turing machine) can be considered as the complex system and its IIT Phi can be measured and improved?
I am reading https://global.oup.com/academic/product/a-world-beyond-physics-9780190871338?cc=us&lang=en& about one approach of complex systems' theory for the emergence of the life. It is ...
0
votes
0answers
94 views
A sort of job scheduling problem
I have been thinking about the following problem:
Let $J$ be a set of jobs that need to be performed. Each jobs comprises of some number ($>1$) of tasks, and a job is considered finished when all ...
0
votes
0answers
13 views
Synthesis of the crisp programs from the Bayesian (probabilistic) programs?
https://arxiv.org/abs/2001.00805 is the article which is pointing towards the direction that the optimal policy of the reinforcement learning can be expressed as the Bayesian/probabilistic program (...
1
vote
1answer
30 views
Upper bound on the average number of overlaps for an interval within a set of intervals
Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded ...
4
votes
1answer
98 views
What should I read to understand semantics of programming languages?
I would like to have a good conceptual understanding of the semantics of programming languages: operational-, denotational-, axiomatic-, categorical-.
Is there a good (standard?) textbook for this?
2
votes
1answer
91 views
Image segmentation of a high resolution 2D binary image into clusters, threads and points
I use python3 script to find out the area proportion of pixel clusters, threads and points in my image. They are originally 8-bit greyscale TIFF images with a resolution of 2048x2168 pixels. I have ...
0
votes
1answer
31 views
Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
1answer
25 views
Clarifying what it means to be Strongly NP-Complete
Wikipedia defines strongly NP-Complete as:
A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
