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

learn more… | top users | synonyms

13
votes
3answers
938 views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" ...
3
votes
1answer
81 views

Maximum size-k cut

Here's my problem, Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and ...
0
votes
0answers
74 views

Communication complexity problems with linear distance

Are there any known (non-trivial) randomized communication complexity lower bounds for natural gap problems in which the 1-inputs are linearly far from the 0-inputs? That is, partial functions ...
0
votes
0answers
65 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
15
votes
1answer
279 views

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
13
votes
1answer
196 views

Permutations with forbidden subsequences

Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition. Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a ...
2
votes
0answers
27 views

Reference for randomized GMD decoding

The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a ...
8
votes
0answers
113 views

Knot Recognition as a Proof of Work System

Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion. Is it possible to use a Decision problem ...
5
votes
1answer
92 views

Survivable networks, directed case

I have been working on a project that turns out to be a special case of the directed version of the survivable network problem. Iterative rounding gives a 2-approximation of the undirected case. I'm ...
0
votes
0answers
31 views

Is integrating a function over a simplex easier than over a general polytope?

I am optimizing a polytope volume computation algorithm by slicing off a small amount simplices from the edges to improve a certain heuristic. In the case when I am simply computing the volume, I can ...
11
votes
1answer
171 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
1
vote
0answers
54 views

Runtime of Gomory's Cutting Plane Algorithm

I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
6
votes
1answer
142 views

Limited number of variable occurrences in 1-in-3 SAT

Is there a known result on complexity class of 1-in-3-SAT with restricted number of variable occurrences? I've come up with the following parsimonious reduction with Peter Nightingale, but I want ...
3
votes
2answers
128 views

Is this covering problem NP-hard?

Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ ...
7
votes
2answers
224 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
3
votes
0answers
39 views

Substitution in Resolution Proofs

Let $F = C_1 \wedge C_2\; \wedge ... \wedge\; C_m$ be a unsatisfiable $k$-CNF on variables $x_1,...,x_n$, where $k$ is constant. Let $x_j\rightarrow x_j^1\wedge x_j^2$ be a substitution that replaces ...
2
votes
0answers
108 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
-2
votes
1answer
73 views

what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
2
votes
0answers
74 views

Variant of set cover problem with symmetric difference instead of union? [duplicate]

I am wondering if this problem has been studied, and in particular if there is an algorithm for it. Consider a universe $\mathcal U$ and a set $A \subseteq U$, and a family of sets $\mathcal F ...
6
votes
1answer
114 views

A bounded-independence variant of the Berry-Esseen theorem

I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is ...
4
votes
0answers
71 views

Random Sampling Threshold to Get a Connected Induced Subgraph

Working on network design this summer I have come across certain applications that have inspired me to ask the following question: Given an undirected connected graph $G=(V,E)$ what is the minimum ...
1
vote
0answers
69 views

“conservative approximate Set Cover”?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$). The task is to approximately cover $L$ with translated, rotated and flipped ...
8
votes
2answers
169 views

Computed circuit complexity of decision problems

Has anyone explored what is the circuit complexity of classic decision problems such as Primes or Graph-Isomorphism for small input size $N$? While most people are interested in the how the scaling ...
12
votes
1answer
249 views

Gentle introduction to the algorithmic aspects of tree-depth

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and ...
2
votes
3answers
115 views

Heuristic with worst-case exponential complexity

I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a ...
5
votes
2answers
253 views

What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
4
votes
1answer
158 views

Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
6
votes
1answer
93 views

Lexicographic perturbation for euclidean shortest path instances?

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such ...
20
votes
1answer
482 views

Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

I encountered the following result during my research. $$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$$ where $m=\omega(\sqrt n)$ and ...
17
votes
1answer
315 views

“Embedding” a language in itself

Main/General Question Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and $$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$ for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we ...
7
votes
1answer
174 views

Embedding a graph in the euclidean space

Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the ...
9
votes
3answers
454 views

Is there algorithmic mathematical analysis?

There are algorithmic graph theory/number theory/combinatorics/information theory/game theory. Is there algorithmic mathematical analysis? According to wiki, mathematical analysis includes the ...
5
votes
1answer
254 views

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
3
votes
2answers
174 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
1
vote
0answers
96 views

Has there been work on formal Semantics for linear algebra?

Could I get some references on formal semantics for a calculus on linear algebra that helps you study matrix or tensor based programming languages? I am looking for anything that encompasses linear or ...
12
votes
0answers
95 views

Which monotone Boolean functions are representable as thresholds on sums?

I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want ...
22
votes
2answers
1k views

Complexity zoo for unary languages

Of course, some complexity results may collapse for unary languages but I wonder if there is somewhere a survey summarizing the known results in this case: a kind of complexity zoo for unary ...
7
votes
1answer
125 views

Formalized priority argument

A priority argument, an important proof technique in recursion theory, was introduced by Friedberg and Muchnik, to solve Post's Problem, i.e., the existence of two r.e. sets that do not Turing reduce ...
1
vote
1answer
83 views

Reference for CTL* logic

I need a reference for CTL* logic (preferably easy to understand). I have gathered some disperse information regarding temporal and CTL logic but I need a more orderly coverage. A chapter of the ...
2
votes
1answer
61 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
10
votes
2answers
216 views

Name the graph class: Disjoint union of a clique and an independent set

Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e. $$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$ The graph class of all such graphs is characterized ...
10
votes
6answers
617 views

Are there any topics in theoretical CS that are more about pure math?

I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed ...
3
votes
1answer
222 views

Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
7
votes
1answer
205 views

Information theory and convex optimization

I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
3
votes
2answers
128 views

Question about an old result of Erdős and Simonovits

My question concerns the following result of Erdős and Simonovits. A graph $G$ is $d$-almost-regular if $d\delta(G)\geq \Delta(G)$. Theorem 1 of the above paper states that a large $n$-vertex ...
2
votes
1answer
61 views

Complexity for single-linkage clustering with max norm

Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} ...
2
votes
1answer
208 views

Knapsack combining sum and product

I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed). A ...
1
vote
0answers
45 views

complexity of factoring multivariate polynomials over Fn

recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka). where is the complexity of factoring multivariate polynomials over ...
4
votes
0answers
188 views

research papers for undergraduate students

The papers presented at conferences like SODA, FOCS are hard to understand for undergraduates. Also a lot of background knowledge is assumed for understanding such papers. Are there any ...
2
votes
0answers
78 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...