Questions tagged [big-picture]
The big picture tag is for a "broad, overall view or perspective of an issue or problem."
194
questions
10
votes
0
answers
201
views
Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?
I am lost in a maze of twisty little type theories, all different.
There are a number of works (textbooks and papers) that discuss pure type theories, and specifically the ones constituting the ...
- 577
7
votes
0
answers
104
views
Why is showing lower bounds for AM communication complexity difficult?
One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
- 576
3
votes
0
answers
98
views
Why do some problems seem to admit a richer family of algorithms than others?
Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each ...
- 803
0
votes
0
answers
74
views
Algorithms with advices of huge precomputed data
My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.
As related to the study, I'm wondering what's known about "precomputation&...
- 689
0
votes
1
answer
49
views
Baud rates applied to human communication
The systems that I design always include large arrays of data acqusistion channels, implemented with an assortment of communication protocols, all running at different speeds. I have always wondered: ...
- 1
3
votes
0
answers
90
views
Complete problems for fast-growing hierarchy classes
I need examples of natural complete problems in classes $\textbf{F}_\alpha$, definition of $\textbf{F}_\alpha$ can be found here. Also in section 6 there are examples for $\omega$, $\omega^\omega$, $\...
- 49
4
votes
0
answers
207
views
What does width $4$ permutation branching program correspond to?
$L$ can be computed by a family of programs over $S_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.
$L$ can be computed by a family ...
- 12.8k
2
votes
0
answers
213
views
Simultaneous evidence for $L\neq NL$ and $P\neq NP$
We believe $L\neq NL$ and $P\neq NP$.
Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
- 12.8k
2
votes
1
answer
243
views
DFSA and NFSA intersection problem
Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.
For unbounded $k$ it is known the problem is $PSPACE$ ...
- 12.8k
0
votes
0
answers
222
views
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
- 12.8k
3
votes
1
answer
135
views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
- 12.8k
4
votes
1
answer
217
views
Is $GCT$ necessarily a negative result program?
$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
- 12.8k
-2
votes
1
answer
184
views
What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?
Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different.
What evidences are there that $PP$ is in $BQP$?
What evidences are there that $PP$ is not ...
- 12.8k
1
vote
1
answer
230
views
Analytic Number theory in TCS [closed]
Are there any applications of analytic number theory in TCS?
- 31
14
votes
0
answers
429
views
What percentage of SODA papers are galactic algorithms?
Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
- 1,757
2
votes
3
answers
491
views
what is a model of computation, mathematically? [closed]
Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
- 301
5
votes
1
answer
237
views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
- 539
44
votes
3
answers
6k
views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
- 541
9
votes
1
answer
338
views
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.
Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.
$\mathsf{...
- 12.8k
9
votes
3
answers
817
views
Why exactly are complexity theorists interested in closed timelike curves?
Context:
There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
- 307
2
votes
1
answer
152
views
Lower bound on alternations needed in $BQP$ versus $PH$ result?
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
- 12.8k
2
votes
0
answers
468
views
Is Combinatory Logic (CL) still relevant for programming language theory?
I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
- 5,255
12
votes
1
answer
4k
views
What is the "question" that programming language theory is trying to answer?
I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which ...
- 5,255
5
votes
0
answers
186
views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example this blog post by Scott Aaronson and this article in Quantum Magazine).
What are some problems that are currently ...
- 12.8k
1
vote
0
answers
276
views
On $BPP$ in $P^{NP}$ and $SETH$
It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers.
Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds?
...
- 12.8k
5
votes
1
answer
152
views
Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$
We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
- 12.8k
3
votes
1
answer
692
views
Possible to do Complexity theory with only counting and Pigeonhole
Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
- 12.8k
0
votes
0
answers
145
views
What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?
In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.
$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
- 12.8k
3
votes
0
answers
149
views
What are the consequences if $W[i]=W[i-1]$?
$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
- 12.8k
1
vote
0
answers
41
views
Monotone complexity of PLP
Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
- 12.8k
3
votes
0
answers
115
views
Does $P=BPP$ say anything about space complexity?
There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to ...
- 12.8k
5
votes
1
answer
337
views
From $PIT\in P$ to $P=BPP$
If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?
- 12.8k
2
votes
1
answer
51
views
Certainty of mutual confirmation over faulty channels?
This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the ...
- 21
4
votes
1
answer
345
views
The Maxwell's Demon and Computer Science
What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
- 583
1
vote
0
answers
30
views
On $PP$ and derandomization
$PP\subseteq P/poly\implies PP=\Sigma_2\cap\Pi_2$ and $EXP\subseteq P/Poly\implies EXP=PP$ $=CH=MA$.
If $PP\subseteq P/poly$ then can $PP=\Sigma_2\cap\Pi_2=MA$ hold? Are there difficulties showing ...
- 12.8k
3
votes
0
answers
265
views
Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?
If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.
What are the best statements we have proved that come close to ...
- 12.8k
1
vote
4
answers
435
views
Is Biological Computation a theme covered by the Theoretical Computer Science?
I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an ...
- 583
0
votes
1
answer
169
views
On polytope lattice points
Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.
Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
- 12.8k
2
votes
1
answer
260
views
Where can I seek help when I cannot understand a research paper? [closed]
Where can I seek help when I cannot understand a research paper? Instead of emailing the author since the paper is long time ago, I am preferring some discussion forum that people exchange ideas on ...
- 121
3
votes
0
answers
222
views
Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?
Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
- 12.8k
2
votes
1
answer
249
views
Fixed parameter tractable Integer Programming and $FPP$
Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
- 12.8k
4
votes
0
answers
164
views
On status of Valiant's $NC^2=P^{\#P}$ provability program?
In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back.
What is the rationale (at ...
- 12.8k
4
votes
0
answers
188
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
- 12.8k
2
votes
1
answer
368
views
On $NP$ and $XP$ classes?
On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.
Below this there is a statement which says $XP\not = NP$ unless $P=NP$.
Is ...
- 12.8k
9
votes
3
answers
817
views
What CS theories are absolutely paramount for someone new to TCS to understand? [closed]
First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science....
- 109
1
vote
0
answers
192
views
P=BPP and derandomizing Vazirani-Valiant?
Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$.
1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction?
2. If not what other ingredients are ...
- 12.8k
1
vote
1
answer
217
views
Unambiguous SAT and sparse languages
What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
- 12.8k
2
votes
0
answers
105
views
On analogies between parallel complexity and polynomial time hierarchy structure?
Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$?
Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), ...
- 12.8k
-1
votes
1
answer
200
views
Can message passing help in GI related problems?
Can message passing algorithms like those used in https://arxiv.org/pdf/1704.00395.pdf be useful in showing GI testing is in P?
Note message passing is prominent in AI and has been tried in decoding ...
- 12.8k
59
votes
6
answers
3k
views
Theoretical explanations for practical success of SAT solvers?
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?
By analogy, the smoothed ...
- 36.9k