# Tagged Questions

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-...

48 views

### Algo for covering maximum surface of a polygon with rectangles

I'm looking to an algorithm to covering maximum surface of a polygon with rectangles. Rectangles have to have a specific width, a rectangle can't overlap an other one and each one has to fit in the ...
41 views

### Analysis of algorithms [closed]

I'm looking at the video http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/ ...
16 views

### Reporting an algorithmic step [closed]

I have an multi-step algorithm, where one of the steps would involve eliminating certain columns from a matrix. Imagine a matrix of 300 columns and I intend to remove 9 columns that would create a new ...
8k 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.
133 views

### Uniform sampling from general simplex with a twist

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
100 views

### On the use of Weisfeiler-Leman refinement in Babai's GI proof

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...
123 views

### Relaxed path decomposition of a graph

Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
94 views

44 views

### Connectedness of semi algebraic set by c.a.d

I do not know whether there is a standard or some traditional ways to decide whether a semi algebraic set is connected or not. One way I know is c.a.d algorithm. I have read some papers of c.a.d ...
20 views

### Counting contingency tables with unary inputs

Given $2$ sequences $A = (a_1,\dots,a_k)$ and $B = (b_1,\dots,b_l)$ of natural numbers. A contingency table is a matrix in $\mathbb{N}^{k \times l}$ with row sums $A$ and column sums $B$. Counting ...
164 views

287 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
94 views

### Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...
80 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
55 views

### Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
301 views

### Irreducible algebraic sets via irreducible polynomials

There are many results about irreducible polynomials over finite fields: we know a cardinality of all irreducible polynomials with given degree, we know explicit examples of irreducible polynomials, ...
296 views

### an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
379 views

### Finding the number of rational points effectively

Consider $\# P$ and $\oplus P$. There is a $\# P$-hard problem: to find number of rational solutions of a system of polynomial equations over $\mathbb{F}_2$. The corresponding $\oplus P$-hard ...
54 views

### Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (...
59 views

### Is there analogs of perlin noise algorithm?

I want to create procedure generated map, but all resources that I found talks about using of "perlin noise" algorithm. Maybe better (higher perfomance, more realistic terrain generation) analogs ...
89 views

### A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
97 views

### Fast Fourier Transforms for non-trigonometric bases

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
39 views

### smallest ball enclosing one point of each color

I have a set of colored points (say 10 colors with 50 points of each color) in a 100-dimensional space. I want to choose one point of each color so that the 10 points are as close to each other as ...
212 views

### Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
34 views

### Comparing product of positive affine functions over integers

Problem Let $f_i: \mathbb Z^n \mapsto \mathbb Z$ and $g_i: \mathbb Z^n \mapsto \mathbb Z$ affine functions and $\mathcal D \subseteq \mathbb Z^n$ a set on which they are all positive. Let $P$ and $Q$ ...
301 views

### A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
86 views

### State of the art for univariate complex polynomials factorization with algebraic coefficients

Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$. ...
291 views

64 views

### Algorithm to calculate moments of uniform distribution on convex polyhedra

There is system of linear inequalities $$Ax \leq K,$$ $$x\geq a, x\leq b.$$ $A$ is $(n\times m)$-matrix, where $n\approx 100$ and $m\approx 10000$, $rank(A)=n$. Suppose that on set of solutions ...
167 views

### “Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
47 views

### Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere

Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
46 views

### Expected number of forward jumps to reach a given quantile of a rv [closed]

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...
140 views

### Find special elliptic curves from j-invariant

Let $E$ be the elliptic curve defined over $GF(p)$ and $j$ be j-invariant of $E$, where $p$ is a big prime number. Also suppose $l$ be small prime number (for example $l<5000$) and $\#E$ denote ...
In this question I have suggested a generalization of the notion of a set of points in the Euclidean plane being in convex configuration to the set of vertices of symmetric weighted graphs via $k$-...