Reference-request is used when the author needs to know about work related to the question.
1
vote
0answers
74 views
Oracles which put integer factorization in P
I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P.
Here is a ...
3
votes
1answer
68 views
k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?
It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see this). Does the converse hold? That is, is every planar bounded treewidth graph the (induced?) subgraph of a ...
11
votes
2answers
216 views
Does the $\mathsf{TC^0}$ hierarchy collapse?
Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?
The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between ...
10
votes
1answer
122 views
What is the minimum required depth of reductions for NP-hardness of SAT?
As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.
My questions is what is the minimum ...
-1
votes
0answers
35 views
Machine Learning Techniques to handle unreliable input
I am finding models/techniques that are specific on handling input that is obtained from another prediction model.
In other words, is to find a model that is doing prediction based on another model's ...
4
votes
0answers
82 views
Who coined the term “empirical entropy”?
I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis.
Shannon defined the entropy of ...
1
vote
1answer
52 views
Are Reversal-bounded Multicounter Machines closed under reversal?
This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines.
Reversal-bounded multicounter machines are described at length in his ...
7
votes
1answer
1k views
Distance between regular languages
I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be ...
4
votes
0answers
59 views
The balls and bins model: bounding the marginal contributions in the m>>n regime
Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$.
Given a set $S ...
4
votes
1answer
106 views
Perfectly matchable edges in a bipartite graph
Consider the following problem:
Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume ...
9
votes
3answers
293 views
History and status of the graph matching problem
Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from ...
5
votes
0answers
43 views
When do $\epsilon$-Nash equilibrium strategies converge to Nash Equilibrium strategies?
Nash Equilibria are uncomputable in general. An $\epsilon$-Nash equilibrium is a set of strategies where, given the opponents' strategies, each player obtains within $\epsilon$ of the maximum possible ...
8
votes
0answers
319 views
Has there been any result which does not have any Natural Proofs?
Alexander Razborov and Steven Rudich's Natural Proofs result is one of the major barriers against proving circuit lower bounds. The paper is almost 20 years old (it was published in 1994).
Has there ...
5
votes
0answers
55 views
Convergence speed in Lévy’s continuity theorem
I suppose the answer to my question follows from the proof of the Lévy’s continuity theorem,
but probably one could suggest me a direct reference to the corresponding answer.
The question is as ...
2
votes
1answer
78 views
Intermediate Problems between FP and #P
Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I ...
4
votes
0answers
116 views
What do we know about $\text{P}^\text{NE}$
I have a $\text{NEXP}$-hard problem, that can be solved by a $\text{NEXP}^\text{NP}$ algorithm using a single oracle call.
So from Hemaspaandra we know it is in $\text{P}^\text{NE}$, giving us
...
-1
votes
0answers
157 views
What are some of the most important **solved** computer science problems?
Knowing the past helps in understanding the future. What are some of the solved (non trivial) problems in CS Theory that have been used most in practice and that every student/researcher/practitioner ...
10
votes
1answer
213 views
Is there a book/survey-paper outlining language class hierarchies, closure properties, etc
I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack ...
7
votes
4answers
508 views
Books/Lecture Notes on Parametrized Complexity
I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
0
votes
0answers
67 views
loop invariants in proving program termination
consider two similar pieces of (pseudo)code:
A:
n = f(x)
for (i = 1 to n) do
begin
....
end
B:
x = 1
while (x != 0) do
begin
x = g(x)
....
end
in case A if ...
10
votes
2answers
452 views
Resources for mathematicians hoping to learn more computer science
Background:
I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, ...
7
votes
2answers
261 views
Does a chordal graph where the size of minimal separators is constrained have name?
An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains ...
6
votes
0answers
159 views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
6
votes
1answer
131 views
Shortest paths perturbation
I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
4
votes
0answers
46 views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of ...
16
votes
5answers
1k views
Why economists should care about computational complexity
When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and ...
3
votes
0answers
97 views
Min Weight Complete bipartite subgraph
Suppose we are given a large bipartite graph with weighted edges, and a small parameter $d$ (e.g. $d$ is 3 or 4).
What is known about the run-time to find the minimum weight complete bipartite ...
4
votes
1answer
105 views
A generalization of the geometric closest pair problem to balls
In one version of the classical closest pair problem, one is given a set $S \subseteq \mathbb{R}^2$ and asked to find distinct $x, y \in S$ such that $\|x - y\|$ is minimized for some norm $\| \cdot ...
6
votes
1answer
147 views
Consequences of OWFs for Complexity
It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
10
votes
0answers
238 views
Complexity of the densest k-subgraph problem on planar graphs
In the densest k-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
9
votes
2answers
126 views
Diophantine equations and complexity classes
LINEAR DIOPHANTINE EQUATIONS
(given natural numbers $a, b, c$, are there natural numbers $x$ and $y$ such that $ax + by + c = 0$?) are solvable in polynomial time.
QUADRATIC DIOPHANTINE EQUATIONS ...
1
vote
2answers
113 views
Chernoff Bounds for settings with limited dependence
Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
-2
votes
1answer
113 views
computing with gates on polar coordinates, functionally complete wrt boolean functions?
this question is inspired by a particular somewhat "natural" physical system specifically constructed to mimic another complex highly-studied physical computing system. (some may astutely guess at ...
6
votes
3answers
114 views
Complexity one-alternation SMT
I'm looking for the complexity of satisfiability of a formula $\forall y_1, \dots,y_n, \exists x_1,\dots,x_m, \phi$ or of a formula $ \exists x_1,\dots,x_m \forall y_1, \dots,y_n,\phi$ where $\phi$ is ...
6
votes
0answers
147 views
Hitting sets with a subfamily
Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects.
A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ ...
4
votes
0answers
62 views
Is linearizability equivalent to consensus problem?
In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), the authors have presented the following statement without references:
Linearizability, however, can be achieved ...
2
votes
0answers
128 views
k-CNF ←→ k-DNF conversion to minimize errors
the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
2
votes
0answers
57 views
General covering approximation
Consider the following integer program (general covering):
$\min c \cdot x$ subject to
$Ax \ge b$,
where all entries in $A, b, c$ are nonnegative and $x$ is required
to be nonnegative and integral.
...
7
votes
0answers
97 views
Simplifying the disjoint union of wildcard strings
Setting: patterns with "don't care" symbols, binary alphabet.
For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$.
We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
16
votes
3answers
358 views
Constructively efficient algorithms without efficient correctness and efficiency proof
I am looking for natural examples of efficient algorithms (i.e. in polynomial time) s.t.
their correctness and efficiency can be proven constructively (e.g. in $PRA$ or $HA$), but
no proof using ...
3
votes
2answers
147 views
Follow-the-leader algorithm in swarm formation: literature on the subject?
In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum ...
0
votes
0answers
56 views
Nonnegative Permanent and Ellipsoidal Method
Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.
This was based on the Ellipsoidal Method.
Finding a Max Cut is the same for Bipartite Graphs as ...
4
votes
0answers
66 views
Guarding paths variant of the Art Gallery Problem
The optimization version of the traditional Art Gallery problem asks for a minimum set of point guards that can be placed within a polygon, such that any point in the polygon is visible from at least ...
13
votes
0answers
218 views
Runtime of Grover's algorithm
What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
2
votes
0answers
201 views
PAC learning and computation over real numbers
I became familiar with the BSS model of computation recently.
I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; ...
4
votes
2answers
130 views
Behaviour of Labelled Markov Processes
Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
3
votes
2answers
90 views
dependent types and higher-order logic applied in the realm of DSLs
(this is a beginner question and English is not my first language)
I am searching for references on using theorem proves based on dependent type theory (or Martin Löf type-theory) and higher-order ...
3
votes
1answer
152 views
How powerful are nondeterministic constant-depth circuits?
A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow ...
7
votes
2answers
403 views
Is adiabatic quantum computing as powerful as qubit computing?
Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following.
Is adiabatic quantum ...
5
votes
1answer
89 views
Step-indexing: Where to begin?
I am about to begin a verification project (for MIPS) with my professor (I am a senior undergraduate) and have been told that the soundness proof for the program logic we need will probably involve ...
