Questions tagged [intuition]
The intuition tag has no usage guidance.
17
questions
3
votes
0
answers
175
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 ...
- 2,080
1
vote
0
answers
33
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,080
2
votes
0
answers
127
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 ...
- 2,080
14
votes
9
answers
1k
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 ...
- 3,993
9
votes
1
answer
4k
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?
...
- 5,165
4
votes
3
answers
626
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,165
7
votes
3
answers
1k
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 ...
- 5,165
15
votes
1
answer
637
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 ...
- 5,165
13
votes
2
answers
1k
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 ...
- 5,165
7
votes
4
answers
661
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 ...
- 2,319
6
votes
1
answer
390
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 ...
- 916
18
votes
1
answer
1k
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 ...
- 1,901
2
votes
2
answers
229
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 ...
- 811
1
vote
1
answer
1k
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
1
answer
383
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 ...
- 1,933
19
votes
5
answers
3k
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 ...
- 387
27
votes
6
answers
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 ...
- 1,528