Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
1,644
questions
2
votes
0
answers
56
views
References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$
In a recent blog post, Lance Fortnow dropped as a little exercise the task of proving $\mathsf{PSPACE} \neq \mathsf{E}$, using the fact that $\mathsf{EXP}$ is the closure of $\mathsf{E}$ under poly-...
- 1,007
1
vote
0
answers
120
views
Testing monotonicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$
I am looking for a property testing algorithem for testing mononicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$ which means that whenever $x \le y$ then $f(x) \le f(y)$ and by $x \...
- 23
4
votes
1
answer
84
views
Solving #SAT through TQBF
I'm not extremely proficient with counting complexity classes, but since #SAT is #P-complete, its decision version, let's call it #SAT(D) (is the number of solutions less than some $k$), is in PSPACE. ...
- 1,680
4
votes
0
answers
60
views
EXPSPACE-complete optimization problems
This is similar to this question but specifically for optimization problems.
Which are some optimization problems that (have corresponding decision problems that) are EXPSPACE-complete?
- 1,680
2
votes
0
answers
39
views
Subsuming Learned Clauses
I’m interested in finding papers about DPLL+CDCL SAT solvers that try to subsume learned clauses. I found this paper on arxiv: Subsumption-driven clause learning with DPLL+restarts.
I’m still studying ...
- 629
1
vote
0
answers
21
views
Fat-finger sequences: sequences of numbers as ids for items which are immune from repetition due to mistyping, etc
In real life I am a Software Quality Assurance Engineer who uses Jira to keep track of stories/bugs/issues, etc... On a given day I deal with hundreds of story/bug/etc ids. These ids are easy to ...
- 349
13
votes
1
answer
224
views
Computational complexity of the elementary theory of finite fields
Let $T_f$ denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, $T_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}...
- 1,099
8
votes
1
answer
206
views
A split-consistency property of a formal language
I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$
For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\...
- 181
4
votes
1
answer
103
views
Smoothed analysis in the Turing machine model
Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
- 2,294
1
vote
0
answers
158
views
In what paper did Dijkstra say "with your hands in your pockets"?
I'm looking for a paper by Edsger Dijkstra (which I've read before) in which he talks about a certain mathematical argument that I can't quite remember what it was, but it was an elementary strategy ...
- 19
0
votes
0
answers
80
views
Channel Capacity & Dependency Graph
A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$.
Assume the ...
- 101
4
votes
1
answer
133
views
Constructing vector valued boolean circuits from boolean circuits
This is a reference request. I'm
interested in the compositional construction of small boolean circuits
for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^n$ for $n >...
- 11.5k
1
vote
0
answers
65
views
Is this kind of "multi-reduction" interesting?
Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an ...
- 2,294
5
votes
2
answers
203
views
The empty tree-word for regular tree languages
Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word?
...
- 489
3
votes
0
answers
49
views
Cuthill - Mckee Guarantees?
I'm interested in the following problem: given $M$, a $p \times p $ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a ...
- 131