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

learn more… | top users | synonyms

3
votes
1answer
188 views

Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
-2
votes
1answer
114 views

A trivial question on hierarchy [closed]

According to wiki we know that $\mathsf{ACC^0\subseteq TC^0\subseteq NC^1\subseteq L\subseteq P\subseteq NP\subsetneq NEXPTIME}.$ Class $\mathsf{ACC^0}$ is included in $\mathsf{TC^0}$ is in ...
-1
votes
1answer
156 views

Why study type theory?

After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general? ...
3
votes
3answers
201 views

Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains

Consider a denotational semantics from simply-typed $\lambda$-calculus into dependent type theory. Is that actually a (trivial) term transformation into that dependent type theory? After all, type ...
7
votes
1answer
700 views

Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and ...
5
votes
1answer
281 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
5
votes
1answer
170 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
1
vote
3answers
344 views

Why is lambda calculus so “function” oriented?

I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function? It ...
5
votes
3answers
144 views

What is the relationship between intuitionistic logic, combinatory logic and lambda calculus?

I've been reading Lectures on the Curry-Howard Isomorphism and it talks about intuitionistic/constructive logic (IL) , combinatory logic (CL) and lambda calculus ($\lambda$c) before moving on to the ...
19
votes
2answers
1k views

What was the original intent for the creation of Lambda calculus?

I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church ...
2
votes
0answers
39 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 ...
7
votes
0answers
102 views

Examples of open problems solved through application of a theorem already known

Are there good examples of reasonable open problems in TCS that had an 'obvious' solution via application of a theorem found in mathematics probably found a few decades earlier but went unnoticed in ...
8
votes
2answers
179 views

Sensitivity-Block sensitivity conjecture - Implications

Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$. The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall ...
2
votes
1answer
201 views

Important papers and open problems in Boolean functions

I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions ...
25
votes
3answers
2k views

Impact of Grothendieck's program on TCS

Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's ...
1
vote
0answers
164 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 ...
1
vote
0answers
134 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 ...
3
votes
0answers
79 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 ...
4
votes
1answer
101 views

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big ...
28
votes
5answers
3k views

The unreasonable power of non-uniformity

From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than $\mathsf{P}$. After ...
4
votes
2answers
153 views

TCS oriented refs/survey on group theoretic word problem

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
-3
votes
3answers
194 views

What structures allow a notion of 'strictness', 'weakness' and 'mildness'?

This is more of a 'meta' question as I cannot give a precise formulation of my question. Consider for example the category of total quasi-orders: we can then distinguish between a 'strict' order ...
4
votes
0answers
127 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 ...
12
votes
5answers
655 views

Should reductions make us more or less optimistic for the tractability of a problem?

It seems to me that most complexity theorists generally believe the following philosophical rule: If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to ...
64
votes
7answers
21k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with ...
0
votes
0answers
122 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 ...
3
votes
0answers
112 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 ...
8
votes
1answer
468 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
12
votes
4answers
3k views

Interesting results in TCS which are easily explainable to programmers without technical background

Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math. In order to show them the beauty of TCS, I'd ...
1
vote
0answers
87 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 ...
21
votes
4answers
1k views

Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. ...
-3
votes
1answer
172 views

“tree-like” vs “DAG-like” resolution

hi all there seems to be a deep/not-much-explored phenomenon in the way that SAT resolution proofs can define a tree and/or a DAG & its relationship to lower bounds/circuit complexity. could there ...
7
votes
1answer
420 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
4
votes
1answer
244 views

Distributive expansion of CNF and implicants

I am looking for references for the following theorems. Theorem 1: Distributive expansion of a CNF formula $P_c$ (product of sums) results in a DNF formula (sum of products) consisting of all prime ...
3
votes
0answers
138 views

sketch of Razborovs 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 ...
236
votes
29answers
152k views

Core algorithms deployed

To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of ...
0
votes
0answers
84 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 ...
13
votes
2answers
546 views

What is theoretical computer science?

What exactly is theoretical computer science? Is it learning to code in various language and making apps in platforms? Or is it just thinking about faster and faster algorithms so that you can achieve ...
15
votes
1answer
576 views

Career in Theoretical Computer Science

I am currently a high school student, interested in theoretical computer science and applied mathematics. I have self taught myself linear algebra and calculus and concrete mathematics. I have a naive ...
3
votes
3answers
476 views

Why do theoreticians in CS use multiple-letter variables?

This is a "dual" question of a popular post on math.se. Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an ...
48
votes
5answers
3k views

Overarching reasons why problems are in P or BPP

Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching ...
10
votes
6answers
596 views

Geometric Interpretation of Computation

Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the ...
11
votes
2answers
244 views

Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

This is a follow up to my previous question: Best known deterministic time complexity lower bound for a natural problem in NP I find it bewildering that we haven't been able to prove any quadratic ...
10
votes
1answer
295 views

Why does the log-rank conjecture use rank over the reals?

In communication complexity, the log-rank conjecture states that $$cc(M) = (\log rk(M))^{O(1)}$$ Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a ...
5
votes
0answers
114 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 ...
12
votes
1answer
637 views

How can I use my computational theory and analysis powers for the greater good?

Outside of academia, what are the uses of my 'powers'? What can I do other than teaching and publishing papers? Where all can I apply my powers? For the sake of argument: Please assume I have a PhD ...
27
votes
7answers
5k views

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
24
votes
13answers
3k views

Complex analysis in theoretical computer science

There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't ...
4
votes
2answers
966 views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
198
votes
10answers
87k views

What is the enlightenment I'm supposed to attain after studying finite automata?

I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...