# Tagged Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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!
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$. ...
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 ...
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 ...
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?
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 ...
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?