# 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,498 questions
Filter by
Sorted by
Tagged with
119 views

### Ramanujan graphs in Polynomial time

I am a research scholar with a computer science background, currently working on graph theory. I am working on a reduction to prove that a problem is NP-complete. I need to include the Ramanujan graph ...
136 views

### Is there an algorithm to generate non-isomorphic Halin graphs?

A Halin graph is a graph constructed by embedding a tree with no vertex of degree two in the plane and then adding a cycle to join the tree’s leaves. We found a list of the number of Halin graphs ...
1 vote
103 views

### Quadratic equations over Gaussian integers

Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ ...
1 vote
51 views

### Some question on Lovett-Meka Discrepancy Minimisation Algorithm

I am reading the paper Constructive Discrepancy Minimization by Walking on The Edges which finds the discrepancy of a set system matching Spencer's bound, in randomised polynomial time. In short, ...
191 views

### Intersecting permutations

Given a subset $P\subset\mathcal{P}_n$ of the permutations of $1,\dots,n$ Question: how can a maximal subset $p\subseteq\lbrace1,\dots,n\rbrace$ be determined, whose elements appear in the same ...
1 vote
99 views

156 views

### The meaning of random number generator test failing

I have a random number generator (number theoretic) that passes all of the NIST tests except the random excursions test. Is there any deep dark meaning to this? To amplify "deep dark meaning"...
1 vote
94 views

156 views

247 views

I was teaching Discrete this semester and set the students loose on a system of linear congruences. One of them came up with this solution. Say $$x \equiv 1 \textrm{ mod } 3$$ $$x \equiv 3 \textrm{ ... 0 votes 0 answers 136 views ### Impact of the global cost function (weighting) to Betweenness Centrality distribution I have a graph whose edges have all a weight of 1. In my particular case computing the Betweenness centrality by counting shortest paths between all pairs results ... 2 votes 0 answers 78 views ### Solving efficiently a quadratic equation in a large finite field of characteristic two I'm trying to solve efficiently a quadratic equation in the finite field \text{GF}(2^{128}) represented as (\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1). Until now, I came across ... 1 vote 1 answer 82 views ### Finding k active elements by evaluating the "any-operator" of subsets of variables Assume a set S of elements \{s_1,\dots,s_n\}, each which has a hidden label 'active' or 'inactive'. Assume there are m\ll n active elements in total. You are allowed to iteratively perform a ... 0 votes 1 answer 26 views ### Edge-length constraints from greedy matching The subject of this question are perfect matchings of a complete undirected graph G(V,E), n:=\mathrm{card}(V)=2k, without self-loops or parallel edges and n=2k vertices. The objective is to ... 3 votes 1 answer 245 views ### How to find the maximum of a sum of squares of sums? Is there any better than a brute force method for finding the maximum$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}... 