Questions tagged [reference-request]

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

1,529 questions
Filter by
Sorted by
Tagged with
13 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 ...
993 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 ...
• 81
62 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
71 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$-...
48 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
47 views
+50

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
55 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 ...
23 views

• 151
58 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 ...
19 views

• 251
370 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 ...
• 191
1 vote
44 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 ...
210 views

• 1,603
87 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 ...
• 251
162 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
59 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,631
130 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
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
39 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,603
1 vote
28 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 ...
• 1,603
51 views

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 ...
• 1,826
181 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 ...
• 217
1 vote
33 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 ...
• 1,603
81 views

• 521
43 views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph. It seems like these problems would fall under the framework of network design problems (...
• 547
208 views

Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
• 600
133 views

Regular Expressions that converts into unambiguous automata

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
• 521
1 vote
58 views

Canonical tester for dense graphs: from tester to removal lemma?

A theorem of Goldreich and Trevisan [1] on property testing in the dense graph model states the following (docusing on the one-sided part): Suppose there exists a one-sided testing graph algorithm ...
• 4,321
It is known that star-free languages are definable by aperiodic syntactic monoids. But is there any algebraic characterisation of star-free safety $\omega$-languages? Edit: A language $L$ is safety if ...