Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
10 views

Dual of cut of embedded graph disconnects surface

Let $G$ be a graph that embedded on a surface of genus $g$, moreover the embedding is triangulated. Let $C$ be a collection of edges that forms a minimal edge cut for $G$. Let $M^*$ consist of the ...
  • 2,267
0 votes
0 answers
20 views

Quantifying the cost of procedures

Is there any research on quantifying the cost of a procedure, with regard to compiler optimization? I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the ...
4 votes
0 answers
80 views

Time Complexity of Pairwise Graph Connectedness

The Setup Consider the following algorithmic problem which, for now, I will call $\mathsf{2GraphConnector}$. Input: A natural number $|V|$, and a finite collection $\mathscr{E} = \left\{E_1, E_2, \...
0 votes
0 answers
88 views

Faster algorithm for sampling unifromly at random

The goal is to come up the simple data structure for sampling a uniform point from a collection of sets, i.e., given a sub-collection $\mathcal{B}$, sample a point in $\cup \mathcal{B}$ uniformly at ...
  • 115
3 votes
0 answers
45 views

Reference for cost of translating between regular language formalisms

It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO). The cost (say in size ...
  • 7,747
2 votes
1 answer
178 views

Are there research papers on related to algorithm fairness in theoretical computer science?

I have seen several articles related to algorithmic fairness in machine learning and AI. I am not able to find out research paper on algorithm fairness in theoretical computer science. Kindly suggest ...
  • 115
3 votes
0 answers
79 views

Linear time in-place stable sort

Surprisingly, linear time in-place stable sort is possible with integer keys of $O(\log n)$ bit length. An algorithm appeared in Radix Sorting With No Extra Space (Franceschini, Muthukrishnan, ...
1 vote
0 answers
106 views

How to measure the weirdness of algorithms?

Let $M$ is a polynomial $k$-tape Turing machine and $C^t(x)$ is a time-bounded Kolmogorov complexity. Let $str_M(x)$ be a string of the following form: $$str_M(x)=w_1^1\# w_2^1 \# ... \# w_{m}^1 ■ w_1^...
  • 49
1 vote
0 answers
54 views

The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
0 votes
0 answers
50 views

Publications on left recursion and PCRE regex engine

Is there any paper (or at least technical report / preprint or even thesis) mentioning that regex engines cannot match expressions that contain "left recursion" (explained below)? I am ...
5 votes
0 answers
97 views

Data structures to store monotone functions

I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$: $$ \forall x \in X: 0 \le x \le N\\ f: X \to \mathbb N\\ \forall x,y\in X:\quad x<...
4 votes
2 answers
157 views

How exactly does a compatible reduction relation change the $\pi$-calculus?

The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial: It is ...
1 vote
0 answers
105 views

Can we describe any context-sensitive language by a grammar without left recursion?

The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
6 votes
0 answers
77 views

Relationship between natural deduction refutation and tableaux for propositional logic

Which kind of relationship is there between natural deduction refutations of a set f propositional logic assumptions, and the corresponding tableaux? For example, consider the unsatisfiable set $\...
  • 1,122
0 votes
0 answers
47 views

Solving sampling problems with circuits?

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
9 votes
1 answer
1k views

Are there survey papers in theoretical computer science?

Are there conferences or journals where we can publish surveys/literature review papers related to theoretical computer science problems? If provide a list of such conferences and journals. I know ...
  • 115
4 votes
0 answers
75 views

Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al. Are there similar results for ($k$-uniform)...
  • 41
2 votes
0 answers
85 views

Reference for complete problems for $FNP^{NP}$

I'm looking for a reference for complete problems for $FNP^{NP}$, i.e., the class of functional problems solvable by a polynomial time non-deterministic Turing machine that has access to an $NP$-...
2 votes
0 answers
59 views

Pebble games and conversions to bounded width circuits

Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits? Here, "conversions to bounded width circuits" means that circuits ...
1 vote
0 answers
60 views

Code indistinguishability assumption for Code based cryptography (in special cases)

Cryptosystems that are based on error correcting codes are often based with hardness of the two problem. Computational syndrome decoding is hard Indistinguishability Assumption (IA): Distinguishing ...
  • 387
2 votes
0 answers
66 views

From formal models to programs - Model Checking

I am reading on Automata, Model Checking and CTL/LTL. I am looking for examples/references/books that help me understand the following: Given a program (for example Python or Java), how can I change ...
0 votes
0 answers
27 views

Minimax computation for classification problems with smooth densities functions

Fix $d=1$, $r \in (0,\infty)$ and a neigborhood $\Omega$ of $0$ in $\mathbb R^d$ and let and let $W^{1,\infty}(r)$ be the Sobolev ball continuously differentiable functions $f:\mathbb R^d \to \mathbb ...
  • 217
0 votes
0 answers
62 views

Algorithms with advices of huge precomputed data

My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work. As related to the study, I'm wondering what's known about "precomputation&...
2 votes
2 answers
148 views

Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

Given: a (long binary) string $\ell$, and a set of (short) strings, $s_1, s_2, ...$ . Can $\ell$ be written as concatenation of the short strings? I am looking for references on: the name of the ...
  • 121
5 votes
1 answer
161 views

Establishing competing memory limits for pushdown automata

Let $L$ be the language of all even-length strings whose first half is a palindrome. Let $L$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $\...
0 votes
0 answers
76 views

Programming languages with constraints on values of variables?

Hi Theoretical Computer Science Stack Exchange, I have been wondering if there are programming languages where one can have constraints on values variables can have? Have such approach been used in ...
0 votes
0 answers
20 views

2-connectivity of dual of a minimal cut in a bounded genus graph

Let $G$ be a graph of genus $g$ embedded on a surface of genus $g$. Let $s,t \in V(G)$. Consider a minimal $s,t$-cut $C$ in $G$. Let $H$ consist of the union of faces adjacent to $E(C)$. Notice that $...
  • 2,267
1 vote
0 answers
32 views

Interval arithmetic adapted to backwards stable problems

In numerical analysis, there are algorithms which are either forwards stable or backwards stable. Forwards stability is strictly stronger, and is more desirable. Unfortunately, it is in many instances ...
  • 293
8 votes
1 answer
164 views

Word equations with integer parameters

This is mainly a reference request. Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows: $$e,e':= w\mid w^i \mid e\cdot e'$$ Where $w\in\Sigma^+$ is a word, and $i$ is an ...
  • 7,747
0 votes
1 answer
55 views

Are there logical devices similar to "existential variables" or "blank nodes" of Semantic Web?

In Semantic Web, alongside permanent names of things also "temporary names" named "existential variables" or "blank nodes" denoted as "_:label" are used. All ...
3 votes
1 answer
94 views

Name for set of vertices that are pairwise within distance two

A 2-stable set (or a distance-two independent set) of a graph $G$ is a set of vertices which are pairwise at a distance greater than 2 in $G$. Is there a name for a set of vertices which are pairwise ...
2 votes
1 answer
124 views

Nondeterministic communication complexity

Let $X$ and $Y$ be finite sets and $f : X \times Y \to \{0,1\}$. I am confused about the definition of the deterministic communication complexity of $f$, denoted $N^1(f)$, or rather about the ...
5 votes
1 answer
205 views

Complexity of Yao's tiling number?

In communication complexity, we encounter the complexity measure $\chi(f)$ for $f : \{0,1\}^{2n} \to \{0,1\}$ which is the minimal number of $f$-monochromatic rectangles needed to tile the $2^n \times ...
9 votes
0 answers
376 views

Examples of simulations in proof complexity that are not p-simulations

I am writing a paper on the complexity of some unorthodox proof systems, where I have two systems $P$ and $Q$ such that $P$ simulates $Q$ in the sense of it being possible to translate a $Q$-proof ...
1 vote
0 answers
46 views

Weak simulation of Clifford circuits

Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the ...
5 votes
1 answer
211 views

Name for words without squared symbols

Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
  • 161
0 votes
0 answers
70 views

Is there a term for 'no-turn-back walk' in graph theory?

Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{...
4 votes
1 answer
90 views

Comparative communication complexity?

I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication ...
7 votes
1 answer
178 views

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

This is what I'm looking for. Take a recursive algorithm: def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) and turn it into ...
  • 293
2 votes
0 answers
64 views

Summing over weighted paths optimally

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications? Is there a name for this problem? This comes up in ...
4 votes
0 answers
135 views

Split a string of positive numbers into substrings with decreasing totals

Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
  • 51
0 votes
0 answers
34 views

Using error-correcting codes in multi-player games

There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
  • 193
1 vote
0 answers
42 views

Cycle double covers of cubic graphs using only a few cycles

This is a reference request question. Let $G$ be an arbitrary cubic graph. Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature? I ...
1 vote
0 answers
32 views

Cycle decompositions of locally linear 4-regular graphs

(Preface) We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$. (Question starts) A graph is locally ...
2 votes
0 answers
53 views

Bin packing with non-additive load functions

I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has ...
4 votes
1 answer
200 views

What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances? I'm only aware of one special case where the extreme points are all ...
  • 215
1 vote
0 answers
38 views

Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?

The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
2 votes
0 answers
84 views

NP-hardness of Euclidean k-Median for k = 2

In the Euclidean $k$-median problem, we are given a set $C$ of clients in $\mathbb{R}^d$. The task is to open a set $F \subset \mathbb{R}^d$ of $k$ facilities such that the cost function $\Phi(F) = \...
2 votes
0 answers
61 views

Are there any references for this theorem of Lercher?

Let $\Delta = \lambda x.(x)x$ and consider $\Omega = (\Delta)\Delta$. Then $\Omega$ is exactly the only $\lambda$-term of the form $(\lambda x.t)v$ such that $(\lambda x.t)v=t\{v\ /\ x\}$. Does ...
  • 121
4 votes
0 answers
74 views

Complexity of detecting general position in the plane?

What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let'...
  • 8,281

1
2 3 4 5
31