0
votes
0answers
46 views

Computing a Levenshtein edit distance between two strings when a particular set of string edits is forbidden

Let's imagine we'd like to compute a Levenshtein edit distance between two strings, $S_1$ of length $n_1$ and $S_2$ or length $n_2$, consisting of characters over a finite alphabet $R$ of size $q$ ...
3
votes
1answer
79 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
2
votes
0answers
23 views

largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature. Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
3
votes
2answers
178 views

Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances. The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
8
votes
1answer
457 views

How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$? ...
20
votes
4answers
1k views

Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an information-greedy secret service which has backdoors to all internet nodes throughout the world which permit him to observe all exchanged data ...
1
vote
0answers
66 views

Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
7
votes
1answer
212 views

Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions: (a) their solution would likely be of some ...
4
votes
0answers
152 views

Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected ...
11
votes
4answers
424 views

Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics? Can we ...
8
votes
2answers
198 views

Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...
2
votes
1answer
158 views

Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways: 1- Mark ...
6
votes
1answer
332 views

Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
0
votes
1answer
242 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...
5
votes
1answer
573 views

How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance. Grover's algorithm ...
2
votes
1answer
431 views

#P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
2
votes
1answer
459 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
7
votes
2answers
834 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
12
votes
1answer
2k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
5
votes
6answers
2k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
2
votes
3answers
2k views

Worst known algorithm in terms of Big-O (more precisely Big-theta)?

Hello, I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
0
votes
0answers
81 views

Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?

I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
2
votes
1answer
177 views

Parsing of Stochastic Contex-Free Grammars (SCFGs)

I am interested in parsing of general SCFGs. I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : ...
8
votes
1answer
1k views

All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it. Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...
5
votes
1answer
323 views

Drawing graphs on circles

Please consider the following problem: Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices. Task: place equidistantly the vertices of $G$ on a circle of unit ...
28
votes
1answer
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 ...
6
votes
1answer
411 views

post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...
2
votes
4answers
698 views

Enumerative algorithm through inclusion-exclusion

Hello everybody ! I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...
3
votes
1answer
462 views

Approximating an integral representation of the Number Partition Problem

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...
2
votes
0answers
252 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
1
vote
2answers
773 views

Practical use of probability amplification for randomized algorithms

Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial ...
2
votes
2answers
328 views

Efficient computation of AB^-1 for matrices

Hi there, Sorry if this has already been asked before. I tried googling for it, but perhaps I could not find the right words to search for. My question is: Which is the fastest way to compute ...
1
vote
1answer
402 views

Number of subset sums

Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset ...
3
votes
4answers
1k views

Does an “efficient” random number generator exist?

Given some number $n$ and a seed number $s$<$n$, I want a random number generator (RNG) that will go through all integers `<$n$ before coming back to $s$. The resulting random number must be ...
4
votes
7answers
1k views

How to generate a net on a 8-dimensional sphere

Using Matlab, how to generate a net of 3^10 points that are evenly located (or distributed) on the 8-dimensional unit sphere? Thanks for any helpful answers!
0
votes
1answer
171 views

Building optimal rewriting rules.

Please give me some pointers where I can learn more about the following problem: I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...
1
vote
4answers
1k views

Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface

Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{min} < r_i < r_{max}$. Here, the ...
1
vote
2answers
758 views

Calculating the surface area distribution of two-dimensional projections for a polytope

My question concerns the existence of a nice (deterministic?) method/algorithm for calculating the distribution of surface areas for two-dimensional projections of an arbitrary polytope (or convex ...
9
votes
2answers
439 views

When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?

To ask this question in a (hopefully) more direct way: Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ ...
30
votes
7answers
2k 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 ...
5
votes
1answer
524 views

Counting Eulerian Orientation in a 4-regular undirected graph

We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 ...
1
vote
2answers
634 views

Find the subset of a line on a sphere “far” from a set of points on the sphere.

I have some code where the "hot part" relies on an inefficient solution to this problem. Problem: I have 3 inputs: a. A collection of N points on the surface of a sphere. b. A line segment on the ...
44
votes
4answers
2k 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 ...
0
votes
2answers
734 views

Travelling Salesman Problem [closed]

Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
5
votes
1answer
1k views

Finding unknown integer-valued polynomials using inequalities

I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here. Suppose you are given the ...
1
vote
1answer
2k views

Closed form of a nonlinear recurrence sequence.

The master theorem seems to fail on nonlinear recursive functions. Is there a standard tool for finding the closed forms of recursive functions of this form? The question comes from trying to find ...
7
votes
2answers
528 views

Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$ This can be done efficiently by linear programming (time polynomial in ...
14
votes
3answers
982 views

does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...
18
votes
3answers
2k views

Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
11
votes
2answers
2k views

How to compute the rank of a matrix?

Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D. Here's the actual ...