Questions tagged [big-picture]
The big picture tag is for a "broad, overall view or perspective of an issue or problem."
32
questions with no upvoted or accepted answers
8
votes
0answers
597 views
How hard is the origin of life problem?
The origin of life problem is the wide-ranging inquiry into the mechanisms underpinning the emergence of life, where one definition of life is "a self-sustained chemical system capable of undergoing ...
7
votes
0answers
189 views
Geometric Intuition behind Locally testable codes
Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
7
votes
0answers
333 views
Examples of non-CSLs not created through diagonalization
Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are ...
5
votes
0answers
160 views
Converse to natural proofs theorem?
Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'.
Is it easy to see the converse 'if there is no $2^{n^\...
5
votes
0answers
270 views
Sketch of Razborov's paper “On the method of approximations”
(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
5
votes
0answers
118 views
conceptual tools for illustrating types of computation?
From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc.
The common theme is ...
4
votes
0answers
117 views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
4
votes
0answers
83 views
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$?
4
votes
0answers
146 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 ...
4
votes
0answers
170 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 ...
4
votes
0answers
161 views
Interaction between metamathematics and combinatorics?
Metamathematics started in the 19th century with the discovery of paradoxes intrinsic to certain axiom systems involving infinite objects; attempts to resolve these paradoxes led to the formulation of ...
3
votes
0answers
133 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]$?
3
votes
0answers
100 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 ...
3
votes
0answers
183 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 ...
3
votes
0answers
210 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$) ...
3
votes
0answers
110 views
minimal languages that “cover” grammar productions
this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
3
votes
0answers
157 views
Randomly Discovered Algorithm/Counterexample
I was reading Scott Aaronson's blog, and one of the comments sparked a question.
"if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular ...
2
votes
0answers
89 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), ...
2
votes
0answers
64 views
Modern tools deterministic communication applications
Partition number, Fooling-set method along with rank method provide important tools to identify deterministic communication complexity of a function. These techniques were identified some decades ...
1
vote
0answers
122 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 ...
1
vote
0answers
247 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?
...
1
vote
0answers
37 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....
1
vote
0answers
170 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 ...
1
vote
0answers
63 views
Analogues of different complexity classes in various models
We suspect following relation:
$$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
1
vote
0answers
287 views
intuition that VP=?VNP is (not?) connected to P=?NP
recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1]
what is an ...
1
vote
0answers
164 views
proving speedup phenomenon does not apply to any open complexity class separations
Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question.
the Blum speedup ...
1
vote
0answers
120 views
looking for notable applications of ASP (Answer Set Programming) in TCS
a recent difficult question of interest to the group[1] by GB has possibly led to verification of a new graph property by dspyz, by use of Answer Set Programming/ASP. via sophisticated logic ...
0
votes
0answers
112 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 ...
0
votes
0answers
168 views
On PP in communication complexity
Aho says $D(f)=O(N(f)N(\overline f))$ where $D(f)$ is deterministic communication complexity and $N(f)$ is non-deterministic version.
Do we know $PP(f)=\Omega(2^{(N(f)N(\overline f))^{O(1)}})$ or $...
0
votes
0answers
81 views
Permanent in Bounded error Quasi Poly time
Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)?
Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly ...
0
votes
0answers
238 views
Observable correlation vs non-observable causality
It is frequent to find statistical studies observing some correlation between two events; this correlation is often interpreted by the medias as a causality relation (e.g. "blue-eyed people have more ...
0
votes
0answers
109 views
Contributions Of Computer Science
I would like to know how is theoretical computer science helping to understand mathematics, physics and biology better in our universe. How is it all merging out and how is theoretical computer ...
