Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
388
questions with no upvoted or accepted answers
29
votes
0answers
1k views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if $EXP\...
21
votes
0answers
1k views
Exact algorithm for NAE-3SAT
The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One ...
19
votes
1answer
291 views
Is there a geometrical picture for adiabatic quantum computation?
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
18
votes
0answers
531 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 ...
17
votes
0answers
826 views
Deeper look at Algorithmica?
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The ...
15
votes
0answers
459 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
15
votes
0answers
341 views
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP}...
14
votes
0answers
209 views
The best known upper bound for two-way probabilistic finite automata with one-counter
It is known that the class of languages recognized by two-way deterministic finite automata with one-counter (2D1CAs) is a proper subset of $ \mathsf{L} $ (deterministic log-space):
A 2D1CA can run at ...
14
votes
0answers
296 views
Pseudorandom functions in ACC^0?
In the lower bound result by Ryan Williams (Non-uniform $\mathsf{ACC}$ circuit lower bounds), there is a mention of "little evidence that Pseudorandom function generators exist in $\mathsf{ACC}^0$. Is ...
14
votes
0answers
262 views
AC0 many-one reduction of Mod_3 to PRIMES?
Let Mod$_3$ be the language of binary strings with the sum of the bits divisible by 3, and PRIMES be the set of prime integers.
In a 2001 paper A Lower Bound for Primality, Allender, Saks, and ...
14
votes
0answers
376 views
Applications of fat shattering dimension in computational geometry
The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-...
14
votes
1answer
603 views
Exact Algorithm for edge labeling problem in DAG
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.
Problem: We are given directed acyclic graph $G=(V,E)$. ...
13
votes
0answers
247 views
historical question: earliest description of beta-normal terms together with "neutral" terms in lambda calculus?
A bit of "folklore" in lambda calculus is the idea of characterizing the class of $\beta$-normal terms inductively as a syntactic category ($R$) defined in mutual induction with an auxiliary syntactic ...
13
votes
0answers
433 views
How can one find the "hard" probability distribution on the input for recursive boolean functions?
Update:
Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
13
votes
0answers
191 views
Name and references for balanced variant of the long code?
The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one ...
13
votes
0answers
529 views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
13
votes
0answers
302 views
Is there any known nontrivial result on QIP systems having a space-bounded verifier?
Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier?
The only paper I know is An application of quantum finite automata to interactive ...
13
votes
0answers
743 views
Online algorithms: open problems
Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in ...
13
votes
0answers
1k views
What is the currently best known algorithm for the transportation problem?
Consider the well known transportation problem:
There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs.
Every node has a integer supply or demand, and the arcs have integer costs, used ...
13
votes
0answers
368 views
Oracle relative to which MA does not have a complete problem?
Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
13
votes
1answer
863 views
Complexity class of this problem?
I am trying to understand to which complexity class the following problem belongs:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
12
votes
0answers
175 views
Regular languages accepted by an automaton with at most one transition per letter
I'm interested in the (very restricted) subset of regular languages for which there is an automaton having the following property: for every letter $a$ of the alphabet, the automaton has at most one ...
12
votes
0answers
298 views
Reference request: exponential growth rates of subsequence-closed languages are integers
This question is migrated from MathOverflow, where it did not receive any answers a year ago.
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
12
votes
0answers
226 views
Categorical semantics for S5 modal logic?
Does anyone know where I can look to find out what the generally categorical semantics of S5 is?
For S4, the answer is well-known: we want a Cartesian closed category with a product-preserving ...
12
votes
0answers
153 views
Is it #P-hard to compute the number of antichains of a distributive lattice?
An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, ...
12
votes
0answers
474 views
Looking for a quotation by Edsger Dijkstra
In one of his papers Edgser Dijkstra makes a statement like:
"What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
12
votes
0answers
170 views
Minimal rare subgraphs
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
12
votes
0answers
321 views
Survey on infinite alphabet automata?
The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using ...
12
votes
0answers
341 views
Directed Sparsest Cut on Planar Graphs?
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
12
votes
0answers
273 views
Conditional density of primes
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.
My question is
about the density of primes when we choose random numbers from a ...
11
votes
0answers
247 views
Bloom filter variant for constant-time subset/superset queries
Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which ...
11
votes
0answers
126 views
s-t connectivity on infinite planar graphs with finite description
I would like to know if the following problem is known and has been studied:
Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, ...
11
votes
0answers
525 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 ...
11
votes
0answers
277 views
What are the most recent developments in small-depth quantum circuits?
Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge:
The power of small-depth quantum circuits. Is $BQP = ...
11
votes
0answers
239 views
Inapproximability of multiterminal cut
In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
10
votes
0answers
254 views
Have people looked for parameterized algorithms for problems that are not in NP?
Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
10
votes
0answers
358 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
144 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 ...
10
votes
0answers
259 views
Depth of bounded fan-in circuits for unbounded fan-in circuits
Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$.
What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size $poly(...
10
votes
0answers
271 views
A super-linear time problem in NL
It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 ...
10
votes
0answers
239 views
Complexity of the min edge-colored cut problem
Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is ...
9
votes
0answers
80 views
Expressiveness of pushdown automata whose stack height sequence is unambiguous
I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
9
votes
0answers
91 views
Reference request: DFA linear-time minimization
What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?
Here’s what I’ve been able to find so far:
The acyclic case has been solved. So any ...
9
votes
0answers
108 views
Graphs with minimal-size induced subgraphs
I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
9
votes
0answers
114 views
Expected value of the evaluation of Boolean circuits of depth $2n$
I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.
Let $C_{...
9
votes
0answers
214 views
Regular expressions of prefixes/suffixes
It is well-known that star-free regular expressions, which are defined by the grammar
$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$
where $a$ belongs to a finite ...
9
votes
0answers
208 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 ...
9
votes
0answers
539 views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.
Is it possible to solve perfect matching problem in linear time for given $...
9
votes
0answers
207 views
References for de-amortization
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
9
votes
0answers
164 views
Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?
D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"On Uniformity Within $\mathsf{NC^1}$" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
($\mathsf{FO}$ ...