We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [algorithms]

Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.

1,138 questions
Filter by
Sorted by
Tagged with
10k views

### Examples of algorithms requiring deep mathematics to prove correctness

I am looking for examples of algorithms for which the proof of correctness requires deep mathematics ( far beyond what is covered in a normal computer science course). I hope this is not too broad.
2k views

### How to be rigorous about combinatorial algorithms?

1. The question This may be the worst question I've ever posed on MathOverflow: broad, open-ended and likely to produce heat. Yet, I think any progress that will be made here will be extremely useful ...
3k views

### What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...
14k views

### How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered. ...
2k views

### improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...
6k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference? Long version of the question: I'm sort of surprised to be asking this, because ...
3k views

### Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples: 1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...
13k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
17k views

### Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
19k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
11k views

4k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
3k views

### Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy. Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
3k views

### An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
2k views

### Is there an algorithm for determining whether an expression involving nested radicals is rational?

Specifically, consider expressions involving integers, addition, multiplication, division, and nth roots for any positive integer n. Is there an algorithm that can determine whether such an expression ...
2k views

### Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
822 views

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
730 views

4k views

### Lower Bounds in Theoretical Computer Science

Besides the classical: you can't do comparison sort with faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must ...
Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$...
For what values of $n$ does the equation $\phi(x) = n$ have at least one solution? Is there any efficient way to check it for a given $n$? It obviously has no solutions for odd $n$. And the smallest ...