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

learn more… | top users | synonyms

1
vote
0answers
104 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
68 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
1answer
81 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 ...
26
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 ...
3
votes
2answers
129 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 ...
0
votes
0answers
83 views

A 'Fourier-like transform' for quaternions

The following question may be of interest to the engineering/computer graphics audience. Consider the non-commutative field $\mathbb{H}$ of quaternions, named after W. Hamilton. The units of ...
-3
votes
3answers
179 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
117 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
641 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 ...
57
votes
6answers
20k 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
117 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
100 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
439 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
4k 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
66 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
136 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 ...
5
votes
2answers
314 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 ...
3
votes
1answer
207 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
135 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 ...
221
votes
29answers
140k 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
79 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
486 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 ...
14
votes
1answer
488 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
465 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 ...
46
votes
5answers
4k 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
580 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 ...
10
votes
2answers
234 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
224 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
111 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 ...
11
votes
1answer
589 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 ...
26
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}$ ...
23
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 ...
3
votes
2answers
825 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 ...
191
votes
10answers
85k 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 ...
10
votes
2answers
1k views

Why is the consensus problem so important in distributed computing?

In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One ...
24
votes
5answers
1k views

Ecology and evolution through the algorithmic lens

The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
2
votes
1answer
513 views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
6
votes
2answers
524 views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
10
votes
1answer
396 views

Speedup from algorithmic advances vs. hardware

I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does ...
4
votes
1answer
271 views

Papers on Prolog-like languages without closed world assumption (CWA)

Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the ...
21
votes
2answers
2k views

Implications of proof of abc conjecture for cs theory

What implications would a proof of the abc conjecture have for tcs? http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
-9
votes
2answers
316 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS ...
12
votes
2answers
538 views

Landscape of interactive proof systems

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively ...
4
votes
1answer
232 views

Surveys in other languages than English

Where can I find surveys in languages than English ? If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be ...
-6
votes
1answer
343 views

why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
7
votes
0answers
517 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 ...
2
votes
2answers
186 views

Discerning the best model for a problem

This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s". What is bothering me is ...
6
votes
3answers
216 views

Asymmetry in Property Testing Definition

Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$. More precisely we want to ...
6
votes
0answers
237 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 ...