Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [reference-request]

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

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

Number of graphs that almost contain a $k$-clique

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$...
rus9384's user avatar
  • 1,664
1 vote
4 answers
166 views

The Hydra Game algorithm

I was recently introduced to the Hydra Game by the youtube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4). In this video, they discuss many variants of the Hydra Game - cut off one ...
SomeCallMeTim's user avatar
0 votes
0 answers
22 views

What are some references demonstrating term enumeration of a constructive set theory?

Short and sweet, I would like to see an example (with some explanation) of a term enumeration of a constructive set theory, mainly because I want to appreciate the difference between that and ZFC. ...
Julius Hamilton's user avatar
0 votes
1 answer
23 views

Resources on Tree Automata Regular Expressions

Is there a text that goes through some explicit examples of converting tree automata to tree regular expressions? I'm working through Comon's "Tree Automata Techniques and Applications", and ...
TomKern's user avatar
  • 103
2 votes
2 answers
54 views

A pedagogic review on the advantage/drewbacks of distributed computing

I need to understand the motivations behind distributed computing, namely the fact to perform a computation by making physically separated computer, connected by communication links, work together. I ...
StarBuck's user avatar
  • 137
1 vote
1 answer
48 views

Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
Noone AtAll's user avatar
0 votes
0 answers
21 views

Textbooks to study machine learning as a TCS/FM/symbolic AI researcher

I work in the fields of theoretical CS, formal verification, and symbolic AI. Here's my DBLP link to have a picture of my background: DBLP Can you suggest me resources (good graduate-level textbooks) ...
Nicola Gigante's user avatar
1 vote
0 answers
28 views

Algorithm for computing $\epsilon$-packings of Sets in Euclidean Space

Let $\epsilon > 0$. For $P\subset \mathbb R^d$, a subset $Q\subset P$ is called an $\epsilon$-packing if: for every $p \in P$ there is a $q\in Q$ such that $d(p,q) \leq \epsilon$, and for every $q,...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
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 ...
rus9384's user avatar
  • 1,664
2 votes
1 answer
53 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$,...
user166511's user avatar
1 vote
1 answer
33 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 ...
Fraïssé's user avatar
  • 821
4 votes
1 answer
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 ...
JimN's user avatar
  • 849
-1 votes
1 answer
114 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 ...
Sillyasker's user avatar
4 votes
0 answers
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 ...
Alex Shpilkin's user avatar
0 votes
0 answers
21 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 ...
pyridoxal_trigeminus's user avatar
1 vote
0 answers
34 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 ...
user6767509's user avatar
1 vote
0 answers
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.
Dynamite's user avatar
2 votes
1 answer
67 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 ...
user avatar
3 votes
1 answer
72 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 ...
Bob Aiden Scott's user avatar
0 votes
0 answers
25 views

Does lambda calculus become covariant if you fix the base type instead of the lambda calculus term?

In category theory, we are taught that polymorphic functions correspond to dinatural transformations, a k a multivariant natural transformations between functors of mixed variance $\operatorname{G} \...
Johan Thiborg-Ericson's user avatar
0 votes
0 answers
17 views

Looking for name of problem similar to Steiner trees but with an RGB balancing constraint (color code decoding)

In quantum computing, there is an error correcting code called the color code where each error in the bulk of the code produces three types of symptoms (one red, one green, one blue). Pairs of errors ...
Craig Gidney's user avatar
  • 5,862
0 votes
0 answers
17 views

Looking for collection of protocol state machines

I'm currently studying structural properties of network and control protocols and their relation to testing. I'm specifically interested in state machines. They would not need to cover the full ...
programonkey's user avatar
1 vote
1 answer
64 views

Memory efficient undo data structure

I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
SmileyCraft's user avatar
0 votes
0 answers
25 views

Reference and code for community discovery algorithms in multigraphs

In order to group unstructured or sem-structured texts for a timeline construction approach, I consider several types of correlations among such texts. These different correlations induce a weighted ...
Max Muller's user avatar
0 votes
0 answers
13 views

Reference request for Unit Clause Based SAT Reduction Rules

I tested my XSAT solver using the 4 pigeons in 3 holes problem converted to XSAT. The pigeon hole instance I give below had 108 variables and 88 clauses after being converted to monotone XSAT. My ...
Russell Easterly's user avatar
1 vote
0 answers
26 views

Resources on designing query languages

I'm looking for resources (books, papers, tutorials) on designing domain-specific query languages. I'm mostly interested in the design of syntax and grammar, rather than the implementation. Any UX-...
Tim's user avatar
  • 111
1 vote
2 answers
73 views

Estimating the number of elements shared in two sets using a random sample

Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
Mike Battaglia's user avatar
2 votes
1 answer
48 views

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
Mike Battaglia's user avatar
0 votes
1 answer
81 views

On hardness of finding total dominating sets in triangle-free graphs

A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
Ankit Gayen's user avatar
2 votes
1 answer
122 views

On hardness of finding dominating sets in triangle-free regular graphs

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
Ankit Gayen's user avatar
0 votes
1 answer
45 views

Introduction to theoretical computer science for research mathematicians

Are there any references on theoretical computer science aimed at people with a background in research mathematics? For reference, I spend my time thinking about category theory and set theory most ...
Alec Rhea's user avatar
  • 101
1 vote
0 answers
183 views

Is there a proof of correctness for CPS translations into Appel's IR?

The IR given in Appel's book (Compiling with Continuations) is certainly well explored and battle-tested in production compilers. I have been able to find several works based on or inspired by it (...
paulotorrens's user avatar
1 vote
0 answers
43 views

Shortest unsatisfiable 3-CNF that can't be refuted with narrow resolution?

Proof width (the size of the largest clause in a proof) plays an important part in refuting an unsatisfiable formula. If a formula has a bounded-width resolution proof of its unsatisfiability, then ...
Soha's user avatar
  • 25
4 votes
1 answer
304 views

Finding a minimum cut with an upper bound on the set sizes

In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible. ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
49 views

Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?

I saw the book suggested here. Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy? I ask since, looking through a pdf copy of the book, I found no matches with "...
Sam's user avatar
  • 143
0 votes
1 answer
127 views

Compiler optimization pass joining identical function definitions together (or specializing them)

Consider this program transformation, in any direction, written in ANF: ...
paulotorrens's user avatar
3 votes
0 answers
162 views

Maximum set cover with non-overlap

Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that: $s_i \in S$ $\forall ...
in_question's user avatar
1 vote
1 answer
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 ...
Juan Meleiro's user avatar
1 vote
0 answers
37 views

What is the type of a type signature?

For example, using GHCi, ghci> f x = x + 1 ghci> :t f f :: Num a => a -> a What is the type of the type signature ...
Rodrigo de Azevedo's user avatar
3 votes
0 answers
19 views

k-compact vectored I/O

I have a practical programming problem that I am struggling to find an optimal algorithm for, in part because I don't know what to call it. The problem concerns vectored I/O (scatter/gather). Consider ...
George Hodgkins's user avatar
0 votes
1 answer
30 views

A proof of the completeness of PLTL (Propositional Linear Temporal Logic)

In what paper(s), textbook(s), and/or classnote(s) can I find a detailed proof of the completeness of a certain proof system for PLTL (Propositional Linear Temporal Logic)?
Evan Aad's user avatar
  • 237
0 votes
0 answers
39 views

How to make a GUI for first-order logic representation?

This idea blows my mind, I would appreciate for any guidance. In essence, the question is how a machine should work to transform any kind of formal logic into its graphical representation (e.g. ...
Danila Nikolaychuk's user avatar
3 votes
0 answers
53 views

Reference request about equivalence of automata / regular expressions up-to a language

The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
Martin Berger's user avatar
2 votes
0 answers
62 views

Modified DPLL for 3-SAT by reducing to 2-SAT

In Boolean Satisfiability of CNF formulae we have $k$-SAT where each clause has at most $k$ literals. It is well known that $k$-SAT is polynomial time reducible to $3$-SAT. It is also well known that $...
vvg's user avatar
  • 135
1 vote
1 answer
46 views

Resources to learn NLP

I am an undergraduate student in mathematics. I have a fair bit of experience with deep learning in computer vision research and am willing to dabble into NLP. I hope that things won't be very ...
The Limit Does Not Exist's user avatar
2 votes
0 answers
31 views

Suggestion for tools/libraries for multi-output boolean circuit minimization?

I am interested in the following problem Input: A boolean function F with n boolean inputs and m boolean outputs. Output: A circuit C implementing F such that C has as few gates as possible. The ...
Agnishom Chattopadhyay's user avatar
1 vote
1 answer
59 views

Encoding "all-except" constraints in CNF

I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
Markus's user avatar
  • 166
4 votes
1 answer
114 views

Building the minimal automaton from the syntactic monoid of a language

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
Nicola Gigante's user avatar
3 votes
0 answers
79 views

Lights-out! on a hex grid with buttons on nodes and lights on faces

Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below: Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
Craig Gidney's user avatar
  • 5,862
2 votes
1 answer
191 views

Determining the minimum number of edges to add to a graph to obtain a clique of size $k$

As part of a hobby project I stubmled into the following question which has me stumped: Given an undirected graph $G = (V, E)$ and an integer $k$, what is that smallest number of edges that need to be ...
CutOnBumInBand's user avatar

1
2 3 4 5
21