Computer Science Weekly Newsletter - Thursday, November 27, 2014

Computer Science newsletter

Top new questions this week: Multiplication in $O(n\cdot \log n)$ I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot ... runtime-analysis   asked by TheEmeritus 8 votes answered by David Richerby 5 votes What is the practical relevance of textbook mutual exclusion algorithms? There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ... reference-request concurrency mutual-exclusion   asked by jkff 5 votes answered by Wandering Logic 3 votes How can I compute an exponential modulo a large integer? Does anyone have the computational power to check whether or not $F(m)^d \equiv m \pmod n$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ... arithmetic multiplication modular-arithmetic   asked by Michael Mudarri 4 votes answered by Gilles 7 votes Substituting "remaining variables" during partial evaluation? In "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler" Yoshihiko Futamura wrote: "[Some] portions of a computation process [...] are not evaluated at partial ... compilers interpreters   asked by Higemaru 4 votes Minimal polynomial reduction of dominating set to max clique Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$ It is well known that it is NP ... complexity-theory graph-theory reductions np clique   asked by Jernej 4 votes Polynomial time algorithms on strings I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ... strings polynomial-time data-compression   asked by Danny 3 votes Balanced Weight Distribution in Bins/Buckets Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which ... algorithms approximation knapsack-problems   asked by laughing_man 3 votes answered by laughing_man 1 vote Greatest hits from previous weeks: Represent a real number without loss of precision Current floating point (ANSI C float, double) allow to represent an approximation of a real number. Is there any way to represent real numbers without errors? Here's an idea I had, which is anything ... binary-arithmetic arithmetic floating-point real-numbers number-formats   asked by Ignus 7 votes answered by jmite 17 votes Are all pseudo-random number generators ultimately periodic? Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end? By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence... randomness pseudo-random-generators   asked by user13675 19 votes answered by Yuval Filmus 30 votes Can you answer these? Separate points inside set I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ... algorithms optimization computational-geometry   asked by Diego Cerdan Puyol 1 vote Does any one know what this problem is called? We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ... terminology sets   asked by user3070752 3 votes Information content of computational problems The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal ... complexity-theory information-theory   asked by Mohammad Al-Turkistany 1 vote

Subscribe to more Stack Exchange newsletters Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com. Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails. Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3