Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [reference-request]

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

2
votes
1answer
156 views

Probability of random variable $X$ less than $max(Y_i)$

For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$. Question : Can we upper-bound the following? $$\mathbb{P}\big(X\...
3
votes
1answer
214 views

Constructing subfields of a finite field

Suppose we have a finite field $\mathbb{F}_{p^n} = \frac{\mathbb{F}_{p}[x]}{<f(x)>}$. I want a deterministic polynomial algorithm to compute all subfields of this field. I think we can do ...
21
votes
5answers
662 views

Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
4
votes
0answers
128 views

Maximize number of edges covered by an independent set of vertices

Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
9
votes
0answers
291 views

Complexity of $k=2$ set packing

I am interested in the best currently known algorithm (in fact, any relevant reference) for the following problem: Given a family of subsets $S_1,S_2,\ldots S_N\subseteq \{1,2,\ldots N\}$, ...
1
vote
1answer
91 views

Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
10
votes
1answer
230 views

Complexity of reachability in linear dynamical systems over finite fields

Let $A$ be a matrix over the finite field $\mathbb{F}_2 = \{0,1\}$ and $x$, $y$ be vectors of the space $\mathbb{F}_2^n$. I am interested in the computational complexity of deciding whether there ...
5
votes
0answers
137 views

Notions of Computability at Higher Type III

I've recently found a very nice survey paper called "Notions of Computability at Higher Type" by John R. Longley. The paper says it is part of a 3-part series, with the 3rd concerning non-extensional ...
7
votes
1answer
278 views

Minimum Spanning tree on a complete “random” graph

Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
2
votes
0answers
93 views

Minimize the product of distances from n fixed points

Given $n$ fixed points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem: $$ \begin{align} \text{mininize} \ \ \ &\prod_{i=1}^n \...
6
votes
1answer
191 views

Number of solutions for a system of linear equations over a finite ring

Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and $b\in R^{m}$. Questions: What is the complexity of counting the number of solutions to the system of equations $...
7
votes
1answer
149 views

What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...
9
votes
0answers
288 views

Typed Lambda Calculus models and denotations

I'm trying to draw a general mental picture about the models and the denotational semantics of the typed lambda calculus, in its different variants. I'm particularly interested in how the semantics ...
10
votes
0answers
119 views

Which convex polytopes have volumes of polynomial bit-length?

A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex ...
15
votes
2answers
1k views

Where to learn more about what Theoretical Computer Science is?

I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this ...
1
vote
1answer
92 views

reference request- property of subset of rows in a matrix

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M ...
12
votes
2answers
190 views

Reference for a class of graphs that preserve subgraph distances when ordered

Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v_1, v_2, \ldots v_n$ in such a way that the graph $H_i$ induced by the vertices $\{v_1, \ldots, v_i\}$ has $dist_{H_i} ...
8
votes
1answer
178 views

Original reference for Huffman shaped Merge Sort?

What is the first publication of the concept of optimizing merge sort by identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then repeatedly merging the ...
3
votes
2answers
132 views

Boundary between decidability and undecidability for small theories

There is a lot of research on the boundary between decidability and undecidability of the halting problem for small models of computation: Turing machines, tag systems, CAs, ... This boundary is ...
3
votes
0answers
193 views

Approximating the VM packing problem

In the wikipedia article on bin-packing it is stated that A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
2
votes
1answer
83 views

Density of multiples

I have an infinite collection of positive integers $n_1,n_2,n_3,\ldots$ and I would like to find the density of the numbers divisible by one or more of these.* If the density does not exist, the ...
4
votes
2answers
497 views

Relation between group theory and information theory

Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory). Question: Is there any paper/survey ...
6
votes
0answers
81 views

Computational depth and p-time hard instances

After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
3
votes
1answer
216 views

List of Pivot rules for simplex methods

Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
7
votes
2answers
223 views

Kth best problem that is NP-hard for K polynomial

A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to ...
4
votes
2answers
166 views

Characterisation of P in terms of register machines

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ...
3
votes
1answer
134 views

Median finding with “green forests”?

I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but ...
8
votes
2answers
260 views

Complexity of testing if a hypergraph has generalized hypertreewidth $2$

A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$. The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a ...
6
votes
1answer
202 views

Minimizing a submodular function given noisy oracle access

Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can ...
4
votes
1answer
81 views

Complexity of propositional LTL with past operators and freeze quantifier?

In "A Really Temporal Logic", by R.Alur and A.Henziger, they introduce an extension of Linear Temporal Logic with a freeze quantifier $x.\phi$, which allows to "give a name" to the current time point ...
6
votes
1answer
168 views

Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
9
votes
0answers
189 views

reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

$\newcommand\iddots{⋰}$In "A simple proof of a theorem of Statman" (TCS 1992), Harry Mairson gives a simple proof of Statman's result that deciding $\beta\eta$-equality of terms in simply typed lambda ...
7
votes
1answer
172 views

On bandwidth of graphs

I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance. I could only find research related to computing the bandwidth, ...
5
votes
0answers
149 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
7
votes
1answer
222 views

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3). ...
4
votes
1answer
234 views

Where is the quote “Informal proofs are algorithms, formal proofs are code” from?

Does anyone know the origin of the quote, Informal proofs are algorithms; formal proofs are code. Its made in Benjamin C. Pierce et al.'s Software Foundations.
0
votes
0answers
68 views

Trade-off between number of spheres and wasted space in covering a 3d object by spheres

Consider the following optimization problem: Input: a 3-dimensional "object" $O$. Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
8
votes
1answer
217 views

3-color a cubic graph such that a MIS receives only two colors

According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary ...
4
votes
2answers
148 views

Constant-time bounds on offline 2-choice hashing?

I'm reading up on cuckoo hashing and came across Michael Mitzenmacher's blog posts on the subject. In his motivation of why cuckoo hashing seems like a reasonable strategy, he mentions a connection to ...
5
votes
0answers
125 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths. Given a graph $G = (V, E)$ ...
6
votes
1answer
175 views

Lower bound on prefix code lengths

For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits: $$ f(n)=\max_{|k|\le n}\left|C(k)\right|. $$ (Note that by taking ...
3
votes
0answers
151 views

Fast Approximation Algorithms for Covering Design

The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ ...
10
votes
1answer
279 views

Introduction to probabilistic automata

Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by ...
9
votes
2answers
365 views

Implementing “Internal” Languages

One of the most practical consequences of the "Curry-Howard-Lambek" correspondence is that the syntax of many lambda-calucli/logics can be used to perform constructions in a sufficiently structured ...
12
votes
1answer
192 views

Is there a survey of the field of quantum automata?

I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review by Hirvensalo, but it sounds too succinct to grasp the topic. ...
14
votes
1answer
756 views

Rabin's “degree of difficulty of computing a function, and a partial ordering of recursive sets”

I am looking for: Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960 Summary: “We attempt to measure ...
13
votes
1answer
499 views

Novel proof of pumping lemma for regular languages

Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the pumping property of regular languages. Namely: for each $L\in\mathcal{L}$, there is an $N\in\mathbb{N}$ s.t. every word $w\...
7
votes
0answers
134 views

Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs

In the 1996 paper "Short Paths in Expander Graphs" by Kleinberg and Rubinfeld, the authors show a randomized polynomial-time algorithm for finding an embedding of a graph $H$ into a graph $G$, if $G$ ...
8
votes
3answers
303 views

Convergence theorem for Genetic Programming?

Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic Algorithm adapted for GP such as (Koza ...
14
votes
1answer
372 views

Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as $$ \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus ...