Reference-request is used when the author needs to know about work related to the question.

learn more… | top users | synonyms

4
votes
0answers
102 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
7
votes
1answer
97 views

A word anticorrespondence problem

A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ ...
1
vote
1answer
67 views

Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs

For a project I'm working on, it would seem useful to have a normal form for deterministic (sub)sequential transducers in which the set of states, $Q$, is partitioned into states, $r \in Q_R$, that ...
1
vote
0answers
85 views

Minimizing a monotone submodular function under a cardinality constraint

I would like to know what the status of the following question is: Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 ...
5
votes
0answers
123 views

The evaluation problem for AC$^0_d$ formulas is in FO

Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem: Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$. Output: $\varphi(a)$ I am looking ...
5
votes
0answers
90 views

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
1
vote
3answers
214 views

List of complexity classes closed under complement

Is there a list of 'natural' complexity classes closed under complement? Some that I could think of are P, ZPP, BPP, NP $\cap$ co-NP, PH, PP and PSPACE but surely there are others. Wikipedia and the ...
1
vote
0answers
51 views

Constraint solving for scheduling code with complex unspillable register classes? [migrated]

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
7
votes
1answer
227 views

Inexact labelled binary tree matching

Does anyone recognise the following problems? Do they have names? Are they hard? If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
4
votes
2answers
198 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
11
votes
6answers
2k views

Book for self study of algorithms in group theory

I am a math major interested on TCS. I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find ...
4
votes
1answer
142 views

Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner?

In the question, Translating SAT to HornSAT, Martin Seymour gives a method due to Joshua Grochow. It transforms 2-SAT into Horn-SAT, by creating a variable for every possible 2-SAT clause. Then, if ...
7
votes
1answer
216 views

Major open problems on polynomial kernel (non) existence

We are not able to settle the (non) existence of a polynomial kernel for a parametrized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non ...
3
votes
1answer
121 views

How to evaluate and compare the performance of algorithms in practice?

Let $A$ be a heuristic algorithm for problem $Q$. I want to evaluate the performance of my algorithm in a specific practical environment and compare it to other algorithms. Is there a rigorous ...
0
votes
1answer
84 views

Lossless Compression Books

I am intrigued by compression techniques and I'd like some recommendations about books to study, specifically, on lossless compression algorithms and data structures. I don't know if there is a ...
1
vote
0answers
113 views

Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region ...
1
vote
0answers
146 views

Tree decomposition for DAGs

Tree decompositions and treewidth are a standard way to measure how close an undirected graph is to a tree. I am studying decompositions of directed acyclic graphs (DAGs), and have come to define them ...
13
votes
2answers
1k views

Status quo of category theory and monads in theoretical computer science research?

Background. I am a bachelor student who is interested in research related to category theory, monads and Haskell, and I want to find a topic for my bachelor’s thesis in that area. I have looked at ...
14
votes
2answers
237 views

Recent TCS publications with philosophical aspects

Many computer science publications from the 1950s and 1960s contain fascinating philosophical speculations on the nature of the mind and the meaning of information in relation to the physical world. ...
10
votes
0answers
84 views

Is it #P-hard to compute the number of antichains of a distributive lattice?

An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, ...
9
votes
0answers
50 views

historical question: earliest description of beta-normal terms together with “neutral” terms in lambda calculus?

A bit of "folklore" in lambda calculus is the idea of characterizing the class of $\beta$-normal terms inductively as a syntactic category ($R$) defined in mutual induction with an auxiliary syntactic ...
6
votes
1answer
254 views

NP-hardness of coloring uniform hypergraphs

Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
2
votes
0answers
89 views

A variant of the tiling problem

A classic tiling problem with Wang tiles has the form: Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints $H,V\subseteq T\times T$, is there a way to tile a $w\times h$ rectangular grid with ...
7
votes
1answer
182 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
0
votes
0answers
89 views

Complexity classes for problems that can be solved only from the length of the input

A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time). ...
6
votes
1answer
152 views

Quantum Hardness of Approximating Lattice Problems

A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum ...
47
votes
7answers
3k views

For which problems in P is it easier to verify the result than to find it?

For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
6
votes
2answers
196 views

FSM transducer sequential composition decidability

this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word ...
0
votes
0answers
32 views

Current review on polygon partition problems

Mark Keil(1) provides an extensive survey of polygon partitioning and polygon covering alrogithms. This survey was written in 2000. Is there a more recent survey on this topic?
10
votes
1answer
190 views

Is it decidable whether the output length of a transducer is bounded by the input length?

The transducers considered here are those Wikipedia calls finite state transducers. The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for ...
2
votes
0answers
73 views

Extended version of the paper “Consistent Hashing and Random Trees” with proofs

I've been reading the following paper: David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
3
votes
0answers
123 views

Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
1
vote
0answers
57 views

Looking for reference proving polynomial-time bounds for A* search under specific conditions

In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic ...
5
votes
1answer
134 views

Generating uniform integers in a range from a random generator with another range

Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to ...
9
votes
2answers
198 views

Matrix vector multiplication algorithm using minimal number of additions

Consider the following problem: Given a matrix $M$ we want to optimize the number of additions in the multiplication algorithm for computing $v \mapsto Mv$. I find this problem interesting ...
20
votes
3answers
511 views

What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
6
votes
2answers
235 views

Algorithm for finding heavy hitters in a weighted stream

The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times ...
0
votes
0answers
47 views

English translation of a paper by Dobrushin & Ortjukov

I'm looking for an English version of Dobrushin and Ortjukov, "An upper bound on the redundancy of the self-correcting schemes built on unreliable elements" I managed to find the Russian version ...
20
votes
2answers
2k views

Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
9
votes
1answer
178 views

What is worst case complexity of number field sieve?

Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of ...
21
votes
1answer
394 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is ...
2
votes
0answers
151 views

Is counting the words in a finite regular language #P-complete?

Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I ...
6
votes
8answers
1k views

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

I recently came across a strange concept and was wondering if this was a known / named concept in the realm of CS. The concept is that you evaluate some computation or logical circuit that takes in N ...
7
votes
3answers
233 views

Is there a theory of computation that takes failure and decay of the computation substrate into account?

There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of ...
1
vote
0answers
50 views

Minkowski decomposition of lattice point cloud

Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$. Is there any known result for the following problem? ...
6
votes
2answers
130 views

Deciding functionality of transducers over infinite words

Given a finite state transducer defining a rational relation over infinite words, it is known to be decidable whether or not the relation is a function, i.e. whether each infinite input word is ...
19
votes
3answers
2k views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" ...
3
votes
1answer
123 views

Maximum size-k cut

Here's my problem, Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and ...
7
votes
2answers
410 views

Communication complexity problems with linear distance

Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions ...
4
votes
0answers
175 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...