Questions tagged [reference-request]

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

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

Sieve of Eratosthenes for factorization: bitwise complexity?

As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, ...
11 votes
2 answers
658 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $...
1 vote
1 answer
29 views

Can equations be simplified with the help of a given set of equations?

There are many posts here and elsewhere asking for algorithms to simplify simple arithmetic expressions. For example, this question asks how to simplify the expression $axc + byc + ayc + bxc$. ...
4 votes
4 answers
332 views

Computer Algebra: Algorithms for solving equations symbolically

As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns ...
0 votes
1 answer
43 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
2 answers
55 views

Tiling a simple polygon with hexagons

Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $...
6 votes
0 answers
36 views

How to find the minimum number of elements to distinguish several given sets?

Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum? For example, given $\{...
17 votes
5 answers
3k views

Regular languages that seem irregular

I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated. So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{...
0 votes
0 answers
27 views

Power of regex extensions [duplicate]

It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
0 votes
1 answer
40 views

Looking for name of a priority queue data structure based on bit-boundary buckets

(Note: cross-listed on stack overflow: https://stackoverflow.com/questions/73362856/looking-for-name-of-a-priority-queue-data-structure-based-on-bit-boundary-bucket) I'm looking for the name of a data ...
12 votes
4 answers
918 views

Getting started with Program Analysis

I'm looking for resources on getting started with program analysis. The only book I've found on the topic is the Nielson & Nielson book. Other than that, it seems like there are only "compiler" ...
1 vote
1 answer
111 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 ...
0 votes
0 answers
9 views

Reference/notes for introduction to (von Neumann) architecture

I am interested in understanding what we mean by a von Neumann architecture and need something at a very introductory level. Does anyone know of any good and readable references or notes that will ...
1 vote
4 answers
488 views

Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
1 vote
0 answers
38 views

Are there any (theoretical-esque) computer science "competitions" at Undergrad level similar to Putnam?

I have searched for a bit eventually arriving at well known websites like codeforces, atcoder, codewars, codinggame or the various OJs. They mostly involve solving tasks where usually the main focus ...
0 votes
1 answer
56 views

Any-goal bidirectional A* pathfinding reference

I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
0 votes
0 answers
25 views

Are there solutions available anywhere for Matt Bishop's Computer Security: Art and Science?

I have been reading Matt Bishop's great textbook Computer Security: Art and Science, but cannot find solutions to the exercises anywhere. Has anyone come across them before on their journey across the ...
1 vote
1 answer
88 views

Solving problems by dynamic programming plus quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $$ x_{k+1} = f(x_k,u_k) $$ where $k \in \{ 0,\dots,N-1 \} $, ...
4 votes
2 answers
180 views

Empirical studies about benefits of Q&A sites for programming

I'm looking for empirical papers which investigate if a user can benefit from Q&A sites like Stack Overflow. I welcome any papers related to this topic, e.g: an experiment, investigating if a ...
1 vote
0 answers
80 views

What's the fastest algorithm for polynomial interpolation in finite field with prime order at points 1, 2, 3, ..., n?

Suppose we have finite field $\mathbb{F}_p$ with prime order $p$. Can we find polynomial in $\mathbb{F}_p[x]$ having given values $a_1, a_2, ... a_n$ at $x=1, 2, ..., n$ in less than $O(n^2)$ ...
1 vote
1 answer
42 views

Counter automata with a bound on the counters?

It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example). However, ...
2 votes
1 answer
94 views

Cellular automata on the Eisenstein integers?

Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus ...
17 votes
4 answers
1k views

Is there a TM that halts on all inputs but that property is not provable?

Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, "unprovable" could mean a "...
0 votes
0 answers
40 views

Solutions for "Operating Systems: Principles and Practice" by Anderson, Dahlin?

I'm self-teaching myself operating systems using the textbook "Operating Systems: Principles and Practice" by Anderson and Dahlin. I am solving the exercises but it would be really helpful ...
1 vote
0 answers
19 views

Reference for the formal definition of sigma protocol

I'm looking for a book that contains the formal definition of sigma protocol (something like: A sigma protocol for a relation $R$ and a challenge space $C$ is... that satisfies the properties of ...
11 votes
2 answers
562 views

Job scheduling with a bottleneck problem

Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a ...
22 votes
1 answer
2k views

Classification of intractable/tractable satisfiability problem variants

Recently I found in a paper [1] a special symmetric version of SAT called the 2/2/4-SAT. But there are many $\text{NP}$-complete variants out there, for example: MONOTONE NAE-3SAT, MONOTONE 1-IN-3-SAT,...
1 vote
0 answers
118 views

References for wearable e-health systems for biosignal based health monitoring [closed]

Ubiquitous computing refers to "information technology and computer power, which in principle pervade all everyday objects" (see Friedewald and Raabe, 2010). A similar form is wearable ...
3 votes
1 answer
63 views

What is the analysis that a heap's optimal branching factor is between 2 and 5?

I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $D$ for a heap satisfies $2 \le D \le 5$, and that it is most likely $3$ or $4$ ...
2 votes
1 answer
104 views

Computing the partition function

Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$? ...
3 votes
1 answer
226 views

Shannon's result that some Boolean functions require exponential circuits

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
19 votes
3 answers
892 views

Recipe book for SAT encodings?

SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific domain,...
16 votes
4 answers
1k views

Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines? I am looking for references/applications. However note ...
1 vote
0 answers
53 views

First piece of code in scientific papers

What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
1 vote
0 answers
108 views

A total order of rectangles related to containment

Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different. ...
3 votes
0 answers
20 views

Is there a comprehensive list of complexity theoretic reductions from and to prime number factorization?

I am interested in the complexity theoretic equivalences of prime number factorization. My interest stems from prime number factorization being one of the few candidates for NPI. I am especially ...
1 vote
0 answers
30 views

Shortest path with vertex capacity

I have an undirected graph where each edge $e=\{u,v\}$ has a positive weight $w_{uv}$ and each vertex $v$ has a positive capacity $c_v$. There are two special vertices: a source vertex $s$ and a ...
2 votes
0 answers
36 views

Quantum Boolean SAT algorithm?

Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms? Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be ...
25 votes
3 answers
3k views

How to read typing rules?

I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always ...
3 votes
1 answer
687 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
0 votes
0 answers
19 views

Big O notation References and Resources

I am new to time complexity, and Big O notation. I have this question pertaining to this code in Python 3.X: ...
1 vote
0 answers
10 views

Circuit class: constant depth, poly-size, bounded fan-in

I'm looking for the name of a certain circuit complexity class. It captures, to me, the idea of "shallow physically feasible circuits". I'm looking for the class of problems with: Constant ...
1 vote
1 answer
42 views

What does type theory as a theory of inductive definitions mean?

Unfortunately copy/paste doesn't work for this paper Inductive Definitions and Type Theory, but here is a snippet. The paper begins by stating: The first sentence of the second paragraph says type ...
3 votes
1 answer
40 views

What is a program analysis technique for tracing assignments (mutations)?

I am looking to write a program analysis for Java programs that tracks assignments and is able to discern: whether a class field (static or not) is read and where the read originated whether a class ...
0 votes
0 answers
29 views

Optimal text/code formatting with alignment constraints

Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. ...
6 votes
0 answers
103 views

Bounded existential polymorphism

In his "Types and Programming Languages", Pierce, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
0 votes
0 answers
12 views

Textbook request for Linear Cellular Automata, if possible with an abstract algebraic approach

I am a final semester pure math undergrad, and I became interested in Linear Cellular Automatas.I became interested after reading Klaus Sutner's article. In the article, a little abstract algebra is ...
6 votes
2 answers
390 views

What are the rules for positive recursive types in dependent type theory?

I've recently started independently learning type theory, using a combination of papers found online and ncatlab.org (but have not worked with category theory), and am about to start reading TAPL. I'...
7 votes
3 answers
868 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 ...
2 votes
1 answer
338 views

Video lectures on type systems

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...

1
2 3 4 5
20