0
votes
0answers
30 views

On achieving the maximal correlation

I am reading the famous paper of Renyi, entitled "On measures of dependence" (see here1). He redefined the maximal correlation in a very general form for both discrete and continuous random ...
4
votes
3answers
114 views

How is math used in computer graphics? [closed]

I'm doing a research paper on the mathematics of computer graphics and animation (3D) and I do not know where to start. What mathematical equations and concepts are used for computer graphics and ...
1
vote
4answers
138 views

Discrete Mathematics books for Computer Science Self-study

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
2
votes
2answers
55 views

Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
1
vote
2answers
61 views

Need help on books on diff. equations/geometry and theoretical computer science

I am looking for recommendation of 3 different books on the following topics: 1.Differential Equations -Ordinary diff. equations -Vector field, transport equations -Equation of wave and heat -Use ...
0
votes
0answers
15 views

algorithm for traversing a fractal in a “maximally ordered” way

consider a multidimensional fractal that can be "traversed" in an arbitrary order. is there an algorithm for traversing a fractal in a "maximally ordered" way? in other words the algorithm has ...
0
votes
0answers
14 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
0
votes
1answer
22 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
4
votes
2answers
102 views

Have action/predicate systems (or similar) been considered in the literature?

Question. Has the following concept, or anything similar, been considered in the literature? Definition. An action/predicate system consists of sets $A$ (the actions) and $X$ (the predicates) such ...
129
votes
14answers
23k views

Is computer science a branch of mathematics?

I have been wondering, is computer science a branch of mathematics? No one has ever adequately described it to me. It all seems very math-like to me. My second question is, are there any books about ...
0
votes
3answers
40 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
6
votes
1answer
132 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
1
vote
2answers
104 views

Books about Turing machines and undecidability

I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. ...
1
vote
1answer
125 views

I'm a CS PhD student. I want to re-study some of college mathematics

I'm a PhD student in CS and I have a fair amount of background in mathematics. But it's been many years since I studied Mathematics in college. I would like to refresh and in many cases, understand ...
9
votes
0answers
166 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
3
votes
1answer
138 views

Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
15
votes
1answer
296 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
2
votes
2answers
452 views

Reference request - Any suggestion for good Abstract Algebra pdf for computer science?

I'm a computer science student and I'm starting to learn Abstract Algebra next week. I'd like to get a suggestions for good PDF book about Abstract Algebra. Thanks!
1
vote
0answers
30 views

Lower bound on building heap.

A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only ...
0
votes
1answer
96 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
5
votes
3answers
5k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
3
votes
2answers
114 views

Is there any book / tutorial where i can get the summary of all engineering math stuff

I studied math with all topics but that was 10 years back and now i have forgot them. Now i need to dive into statistics field and machine learning stuff. Now i don't have time for study different ...
1
vote
5answers
650 views

Mathematical notation for computer science

Can anyone point me in the direction of good introductory material on the use of mathematical notation in the field of computer science? I often come across notation in research papers that I don't ...
5
votes
4answers
183 views

Mathematics of computation

What is a good introduction to turing machines, complexity classes, P=NP etc from a purely mathematical viewpoint? I want to know how computation relates to provability in mathematics, I need the ...
3
votes
2answers
142 views

List of the minimal addition chains

The question of finding the Minimal Addition Chain (MAC) for needed for Addition chain exponentiation seems to be NP-complete. As such, it would be nice to have a list for the small powers already ...
2
votes
3answers
202 views

Games with human edge [closed]

Which are some two- or one-player games, where humans far outperforms the best computer programs? And how does the relative edge scale with time allowed to think? (In time frame 1 sec to 8 hours per ...
4
votes
2answers
303 views

Does the $k$th forward difference of Radó's $\Sigma$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and let $\Delta[\Sigma]$ denote the forward difference of $\Sigma$, such that $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. ...
2
votes
1answer
210 views

Where to find $\lambda$-calculus examples? For instance, how to check if a list is empty?

I'm trying to remove many layers of dust from my knowledge about $\lambda$-calculus, without my notes from classes (several hundreds of km and 5 years away). I was trying to understand the examples ...
1
vote
1answer
94 views

good books for networking [closed]

I am looking for a good book for data networks in general, such as internet and wireless networks specifically. In particular, I'm looking for something that provides a good match of theoretical ...
11
votes
2answers
9k views

What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics? Is something like "Introduction to discrete Mathematics" enough?
1
vote
2answers
96 views

Survey Article on Decision Tree Proofs

I'm looking for a survey article on proofs using decision trees. Presumably it would include at least a passing reference to the proof that the lower bound on comparison-based sorting is ...
1
vote
2answers
110 views

Class of linearly parsable languages?

Is there name for class of languages exactly such that their words can be parsed in $O(n)$ by program in conventional Turing-complete language (SML)? (i.e. without backtracking) Any references?
0
votes
0answers
59 views

Survey of balanced languages/grammars etc

Is there any good survey of nested/balanced/parenthesed/bracketed/XML/Dyck/Floyd languages/grammars and their applications? If no, can you please list all relevant keywords to allow gathering all ...
3
votes
2answers
323 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...