Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,564
questions
0
votes
0
answers
23
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
- 101
2
votes
1
answer
120
views
Examples for Real-time vs Linear time
A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
- 121
4
votes
2
answers
158
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 397
2
votes
0
answers
39
views
Submodular function minimization over integer lattice
Let $[k]=\{0,1,\ldots,k-1\}$.
A function $f:[k]^n\to \mathbb{R}$ is submodular if $f(x)+f(y)\geq f(\max(x,y))+f(\min(x,y))$ for all $x,y\in [k]^n$. Here $\max$ and $\min$ are applied coordinate-wise.
...
- 4,327
2
votes
1
answer
92
views
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
- 8,223
9
votes
2
answers
208
views
Defining regular language classes with disjoint union
Regular languages are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for ...
- 8,223
4
votes
0
answers
42
views
Error analysis of Estrin's method
Estrin's Method is an alternative to Horner's method for evaluating polynomials. To evaluate a polynomial $P(x)=\sum_{i=0}^7 a_i x^i$ at a point $x\in\mathbb R$, it first computes the powers $x^2$ and ...
- 898
6
votes
1
answer
239
views
Relationship between the transition monoid of an automaton and its adjacency matrix
Let $A=(Q,\Sigma, \Delta, q_0, F)$ be an NFA over an alphabet $\Sigma$, $M(A)$ be its transition monoid.
For all $a\in\Sigma$, let $S_a\in\mathbb{B}^{|Q|\times|Q|}$ be the adjacency matrix of $A$ ...
- 1,416
18
votes
0
answers
253
views
Can we do integer addition in linear time?
Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:
Input: A sequence of nonnegative integers $\langle X_i:i<k\rangle$ written in binary.
Output: ...
- 15.4k
5
votes
1
answer
157
views
Stronger "induction" principles than induction-recursion
Are there type theories in the literature with "induction" principles stronger than induction-recursion? This answer gives System F as an example of a theory stronger than MLTT + induction-...
3
votes
0
answers
62
views
Exponential version of $CC^0$
(In this question, "uniform" will mean $DLOGTIME$-uniform.)
In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential ...
- 1,015
3
votes
1
answer
127
views
Treewidth for hypergraphs that specify connectedness requirements
This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
- 8,223
3
votes
0
answers
68
views
Bounding the size of a power of a proper interval graph
Is there a citable proof of the following result (or perhaps a generalization of it)?
Lemma 1. Let $G=(V, E)$ be a proper interval graph. Let $G^k=(V, E^k)$ be the $k$th power of $G$. Then $|E^k| = ...
- 9,515
1
vote
2
answers
197
views
How much information does it take to specify, not each member of a group, but any one member?
It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
- 1,697
3
votes
0
answers
91
views
Succinct problems over uniform computational models
For a language $\Pi$, the traditional definition of "Succinct-$\Pi$" is the set of encodings of circuits whose truth tables are members of $\Pi$.
This definition is essentially restricted (...
- 1,015
1
vote
0
answers
77
views
Alternative notions of bisimulation
Suppose $(S, \Lambda, \rightarrow)$ is a labeled transition system. A bisimulation is a relation $R \subseteq S \times S$ s.t. $\forall \alpha \in \Lambda$ and $\forall p, q \in S$ with $R(p,q)$,
$\...
- 11
2
votes
0
answers
103
views
Faster algorithms to estimate the subset sizes
Lemma: Consider two sets $B ⊆ U$, where $n = |U|$. Let $ξ, γ ∈ (0, 1)$ be parameters, such that
$γ < 1/ \log n$. Assume that one is given an access to a membership oracle that, given an element $x ∈...
- 41
2
votes
0
answers
38
views
Algorithms for parametric matroid optimization
Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for ...
- 4,327
0
votes
0
answers
55
views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.
Problem assumptions/definitions:
We have finite number of items I with weights [0, ...
- 101
1
vote
0
answers
104
views
Fastest algorithm for non-empty bins
Assume we have $n$ bins, and exactly $k>0$ of them, are non-empty. Furthermore, assume that we can check if
a specific urn is empty in constant time. I am looking for a randomized algorithm that ...
- 41
2
votes
0
answers
51
views
Has there been any research on faster tensor inner products?
Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.
That got me wondering has anyone looked at the more general problem of faster tensor multiplication? ...
- 369
1
vote
0
answers
45
views
Diameter queries for stream of points
Given an online stream of $k$ points $x_1, x_2,\ldots,x_k$ with $x_i \in \mathbb{R}^2$. By online we mean that when $x_i$ arrives we have no knowledge of points $x_j$ for $j > i$. Denote by $S_i$ ...
- 11
3
votes
0
answers
20
views
Modelling channels without specifying input alphabets
The standard mathematical model of a communication channel is that of a stochastic matrix $(C(x|a))_{a \in A, x \in X}$, where $A$ is the input alphabet and $X$ the output alphabet.
This definition ...
- 131
4
votes
0
answers
73
views
Lower bound on the size of Skolem functions
Consider a quantified Boolean formula $f$. We can convert it into Skolem Normal Form formula $f^*$ such that $f$ is satisfiable iff $f^*$ is satisfiable, by replacing variables that are existentially ...
0
votes
0
answers
59
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 101
2
votes
1
answer
71
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 $C^*$ consist of the ...
- 2,299
0
votes
0
answers
26
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 ...
- 111
4
votes
0
answers
90
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, \...
- 41
0
votes
0
answers
94
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
4
votes
0
answers
51
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 ...
- 8,223
2
votes
1
answer
193
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
87
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, ...
- 2,402
1
vote
0
answers
114
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
58
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 ...
- 597
0
votes
0
answers
51
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 ...
- 11
5
votes
0
answers
101
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<...
- 151
4
votes
2
answers
160
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 ...
- 313
1
vote
0
answers
113
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 ...
- 11
6
votes
0
answers
81
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,416
0
votes
0
answers
50
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 ...
- 21
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
77
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
92
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$-...
- 869
2
votes
0
answers
61
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 ...
- 689
1
vote
0
answers
62
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
76
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 ...
- 59
0
votes
0
answers
28
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 ...
- 291
0
votes
0
answers
71
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&...
- 689
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
163
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 $\...
- 151