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
0answers
28 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 (...
5
votes
1answer
156 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 ...
3
votes
1answer
92 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, ...
1
vote
0answers
51 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 ...
7
votes
2answers
133 views

Algebraic characterisation of star-free safety languages

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 ...
0
votes
0answers
69 views

Large CLIQUE approximation

I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices. ...
3
votes
0answers
59 views

Exact FPT Algorithm for Continuous Euclidean $k$-Means

The continuous Euclidean $k$-means problem is defined as follows: Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
2
votes
2answers
107 views

Status of certain problems in knot theory

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
-1
votes
0answers
52 views

Kolmogorov complexity with limited calculation time - edited

EDIT: After receiving the comment of Emil Jeřábek, I posted a more advanced question on a related topic, please also have a look at it. ORIGINAL QUESTION The Kolmogorov complexity of a string is the ...
0
votes
1answer
93 views

Diophantine equations with bounds on variables

Solving Diophantine equations is famously known to be undecidable. What about Diophantine equations to be solved over a finite domain? In particular, if I put an upper bound $k$ over the value of the ...
0
votes
0answers
53 views

EXPSPACE-complete problems involving numbers

This is a subset of this question. I'm looking for EXPSPACE-complete problems, for using in a reduction, which involve numbers in some ways, since my target problem involves numbers and linear ...
0
votes
0answers
71 views

Low-Treewidth Sorting Networks

It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
2
votes
1answer
91 views

Property testable in sublinear time in bounded degree graphs but not in general graphs

Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...
1
vote
1answer
203 views

Is this a novel technique for determining whether or not two rotated rectangles collide?

I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm: Rotate both rectangles by the negative rotation ...
1
vote
0answers
83 views

Input length and calculation time to simulate a quantum measurement

Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...
4
votes
1answer
108 views

What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?

The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9). Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if $(\Omega,\...
-3
votes
1answer
105 views

Can I research in web technologies with an academic approach?

I'm an undergraduate computer engineering student. I know that I like to become a researcher in my major in the future. I also work as a junior web developer at a small start-up, and I think I really ...
4
votes
1answer
191 views

Does this notion of entropy have a name?

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
1
vote
1answer
110 views

Communication complexity of reconstructing a random bit-string of length $n$

This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to ...
2
votes
0answers
65 views

Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System

(One formulation of) Ramsey's theorem states that any colouring of edges of the complete graph with $4^n$ vertices with two colours will contain a monochromatic clique of size $n$. I am new to proof ...
10
votes
1answer
223 views

Succinctness of regular expressions with empty word

Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$ These $\varepsilon$⁻free expressions can define all regular languages ...
0
votes
0answers
44 views

Low Rank Approximation of a hidden subset

Let $P$ be a set of $n$ points in $\mathbb{R}^d$ and $Q\subseteq P$ with $\vert Q\vert \geq \alpha n$ for some constant $\alpha\in(0,1]$. Given a $j$-dimensional affine subspace(flat) $F$ consider the ...
1
vote
1answer
135 views

The "electricity packing" problem

In a distant village, there are $n$ electricity consumers. Consumer $i$ has a power demand of $d_i$ watts. The total electricity supply is $s$ watts. If $s\geq \sum_{i=1}^n d_i$, then all consumers ...
1
vote
0answers
38 views

A variant of k-median clustering

Suppose $\mathcal{P} =\{P_1,\cdots,P_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c_1,\cdots,c_k\}$ of $k$ points, consider the follwoing objective funtion $cost(\mathcal{P},C)...
2
votes
0answers
67 views

Reference request: characterisation of simultaneous substitution

For simply typed λ-calculus, a simultaneous substitution from $\Gamma$ to $\Delta$ is concretely a type-preserving map from variables in $\Delta$ to terms in $\Gamma$. See, for example, Programming ...
1
vote
0answers
136 views

How can I find the PhD thesis of A. V. Kostochka?

I've searched for the doctoral thesis of Alexandr V Kostochka in internet but couldn't find it. Can somebody help me? I have searched in his publications list (which contains only one article ...
4
votes
0answers
86 views

Complexity of inclusion of transfinite expressions

Transfinite expressions on an alphabet $\Sigma$ are generated by the grammar : $$e,f:= a\in\Sigma\mid e\cdot f\mid e+f\mid e^*\mid e^\omega.$$ They describe languages of transfinite words, i.e. words ...
1
vote
0answers
37 views

Full version of the paper "Characterization of Temporal Property Classes"

Look at this paper: E. Chang, Z. Manna, A. Pnueli. "Characterization of Temporal Property Classes" The proof of Theorem 8 at page 8 says: "We will outline the proof which appears in the ...
2
votes
2answers
112 views

Translation of Counter-free automata into Linear Temporal Logic

There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a ...
0
votes
0answers
66 views

"Fast" approximation algorithm for geometric hitting set of same-height rectangles

In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects. ...
0
votes
0answers
99 views

Can the rendezvous problem be solved without exploration in synchronous rings?

Problem Definitions: Rendezvous: A number of agents, in this case two, that start from distinct nodes of a ring need to meet in some node that is not known in advance. (Collaborative) Exploration: A ...
3
votes
1answer
149 views

TSP with "enemy" nodes

I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for. The story/idea ...
1
vote
0answers
38 views

program search with optimization methods for (resource bounded) Kolmogorov complexity

Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
1
vote
0answers
50 views

sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
3
votes
1answer
101 views

Hardness when restricted to an infinite number of far apart instance sizes

Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance ...
0
votes
1answer
89 views

Reference for context-free grammar for Martin-Löf type theory

Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
7
votes
0answers
149 views

Where is Yao's original proof that distinguishers imply next-bit-predictors?

In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...
3
votes
1answer
255 views

Proof and computational complexity

I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
1
vote
0answers
36 views

What is known about the stabilizer rank of this simple state?

Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$, $$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$ What is known or conjectured about the stabilizer ...
0
votes
1answer
70 views

Given a partition and an element, find the subset that includes this element

I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
4
votes
0answers
67 views

Terminology for languages of pairs of words

I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this? I wrote "double language" first (but that doesn't sound right to me), then &...
3
votes
1answer
97 views

Approximating Independent Dominating set on bipartite graphs

I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices. My question is: are there any positive results in the ...
3
votes
0answers
62 views

Multi-round communication complexity of greater than

For the "greater-than" problem in Yao's 2-party communication complexity model, Alice receives $X$ and Bob receives $Y$, and they need to decide whether $X>Y$. I recently listened to an (...
7
votes
1answer
395 views

Strongly normalizing type theory beyond induction-recursion

Are there known type theories in the literature, which have strong normalization proofs and their proof-theoretical strength goes beyond strength of type theories with induction-recursion?
4
votes
0answers
80 views

Relative consistency of various Martin-Löf style type theories

I am wondering about relative consistency of various Martin-Löf type theories, when compared to one another, I will use MLTT for the intensional Martin-Löf type theory with $\Pi$, $\Sigma$, $\mathbb{N}...
1
vote
2answers
105 views

Name of this graph partitioning problem? (related to coloring)

Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(...
4
votes
0answers
104 views

Trading treewidth for depth in Boolean circuits

We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is ...
4
votes
2answers
255 views

Density of semantics in syntax

Let $L$ be a programming language, and $\cong$ a notion of equality of $L$-programs (in general $\cong$ will be undecidable). Let $syntax(n)$ be the number of $L$-programs of size $n$ (for some ...
7
votes
0answers
156 views

A variant of transfer learning

Suppose we want to train $K$ linear classifiers based on iid samples. Each classifier is of the form $x\mapsto\mathrm{sign}(w\cdot x+\theta)$, with the constraint that the hyperplane $w$ is the same ...
0
votes
0answers
25 views

Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$. In the problem I am trying to solve, in a sequential fashion, we obtain a ...

1
2 3 4 5
30