Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
400
questions with no upvoted or accepted answers
29
votes
0
answers
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\...
19
votes
1
answer
294
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 ...
- 441
18
votes
0
answers
534
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 ...
- 367
17
votes
0
answers
864
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 ...
- 18.7k
15
votes
0
answers
463
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 ...
- 2,237
15
votes
0
answers
342
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}...
- 16.3k
14
votes
0
answers
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 ...
- 3,647
14
votes
0
answers
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 ...
- 1,334
14
votes
0
answers
264
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 ...
- 18.7k
14
votes
0
answers
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-...
- 31.7k
14
votes
1
answer
606
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)$. ...
- 333
13
votes
0
answers
250
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 ...
- 4,309
13
votes
0
answers
438
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 ...
- 395
13
votes
0
answers
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 ...
- 50.2k
13
votes
0
answers
530
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)$ ...
- 566
13
votes
0
answers
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 ...
- 3,647
13
votes
0
answers
757
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 ...
- 131
13
votes
0
answers
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 ...
- 970
13
votes
0
answers
369
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 ...
- 3,614
13
votes
1
answer
872
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 ...
- 2,186
12
votes
0
answers
181
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 ...
- 7,455
12
votes
0
answers
302
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 $...
- 319
12
votes
0
answers
238
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 ...
- 31.6k
12
votes
0
answers
162
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, ...
- 7,455
12
votes
0
answers
475
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 ...
- 87
12
votes
0
answers
172
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 ...
- 151
12
votes
0
answers
323
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 ...
- 4,493
12
votes
0
answers
343
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 ...
- 426
12
votes
0
answers
275
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 ...
- 21.3k
11
votes
0
answers
257
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 ...
- 199
11
votes
0
answers
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, ...
- 22.3k
11
votes
0
answers
528
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 ...
- 10.8k
11
votes
0
answers
280
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 = ...
- 960
11
votes
0
answers
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 ...
- 1,414
10
votes
0
answers
262
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 ...
- 101
10
votes
0
answers
363
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 ...
- 668
10
votes
0
answers
146
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 ...
- 7,455
10
votes
0
answers
262
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(...
- 21.3k
10
votes
0
answers
273
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 ...
- 3,647
10
votes
0
answers
243
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 ...
- 101
9
votes
0
answers
371
views
Examples of simulations in proof complexity that are not p-simulations
I am writing a paper on the complexity of some unorthodox proof systems, where I have two systems $P$ and $Q$ such that $P$ simulates $Q$ in the sense of it being possible to translate a $Q$-proof ...
- 191
9
votes
0
answers
87
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,...
- 7,455
9
votes
0
answers
93
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 ...
- 414
9
votes
0
answers
110
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$-...
- 7,455
9
votes
0
answers
116
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_{...
- 4,721
9
votes
0
answers
217
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 ...
- 151
9
votes
0
answers
210
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 ...
- 4,309
9
votes
0
answers
553
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 $...
- 99
9
votes
0
answers
208
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 ...
- 525
9
votes
0
answers
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}$ ...
- 21.3k