# Questions tagged [big-picture]

The big picture tag is for a "broad, overall view or perspective of an issue or problem."

190 questions
Filter by
Sorted by
Tagged with
54 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&...
35 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
65 views

• 12.5k
674 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 ...
143 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.5k
377 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,157
2k 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,157
171 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.5k
1 vote
268 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.5k
87 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$?
• 12.5k
658 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.5k
138 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.5k
145 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.5k
1 vote
39 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.5k
112 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.5k
303 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.5k
49 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
304 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 ...
1 vote
26 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.5k
236 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.5k
1 vote
398 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 ...
147 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.5k
243 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
221 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.5k
1 vote
239 views

• 12.5k