Questions tagged [intuition]
The intuition tag has no usage guidance.
3
votes
0answers
126 views
Fast way of getting a matrix of sums
We are given an array of variables $A$, along with a matrix $M$. The elements of the matrix $M$ are composed of sums of the variables in $A$. We are allowed to pre-process $A$ in order to find a ...
1
vote
0answers
30 views
Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?
In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime.
I've been toying with an idea for a ...
2
votes
0answers
111 views
What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?
There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
13
votes
9answers
891 views
Counterintuitive results for undergraduates
I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get ...
5
votes
1answer
1k 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
470 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 ...
7
votes
3answers
765 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 ...
15
votes
1answer
514 views
Why was Schönfinkel's work on eliminating “bound variables” in logic so crucial?
AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
12
votes
2answers
811 views
How exactly does lambda calculus capture the intuitive notion of computability?
I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"?
"Intuitively" I get the computability model of Turing ...
7
votes
4answers
523 views
Explaining computer science algorithms/concepts/ideas using metaphors
Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
6
votes
1answer
373 views
Would an optimal sorting network ever have to swap two numbers the “wrong” way
Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the ...
16
votes
1answer
611 views
Splay tree potential function: why sum the logs of the sizes?
I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
2
votes
2answers
143 views
How are PCPs and ZKPs related?
I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge ...
1
vote
1answer
894 views
Primal vs dual decomposition methods
I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
2
votes
1answer
370 views
An intuitive justification - Metric Embedding Based Approximation Algorithms
Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course offered at CMU .
I had a very basic question from the very first lecture of this course ...
18
votes
5answers
2k views
Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?
It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.
This can easily be understood inductively using oracle machines.
The question ...
27
votes
6answers
2k views
How do you get a “Physical Intuition” for results in TCS?
I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS.
For example, linear algebra can be understood geometrically, or in terms ...
