Questions arising from applications of theoretical computer science in other areas of computer science research/practice or other subjects.

learn more… | top users | synonyms

3
votes
2answers
110 views

TCS oriented refs/survey on group theoretic word problem

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
5
votes
0answers
123 views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
2
votes
1answer
107 views

Fast algorithm to distribute points evenly in a 2D grid

In an NxN grid, I want to select M points ($1 \leq M \leq N^2$) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. Can you suggest a fast algorithm for ...
1
vote
0answers
58 views

looking for notable applications of ASP (Answer Set Programming) in TCS

a recent difficult question of interest to the group[1] by GB has possibly led to verification of a new graph property by dspyz, by use of Answer Set Programming/ASP. via sophisticated logic ...
20
votes
4answers
989 views

Justifying asymptotic worst-case analysis to scientists

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. ...
1
vote
1answer
196 views

finding “hubs” in a graph

consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ ...
215
votes
30answers
134k views

Core algorithms deployed

To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of ...
5
votes
0answers
109 views

Exploring a DFA, with no feedback

Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
12
votes
1answer
126 views

Detecting circuit that's similar in functionality and implementation

Let $x=(x_1,\dots,x_n)$ be a vector of boolean variables. Let $C,D$ be two boolean circuits on $x$. Say that $C$ is similar to $D$ if: $\Pr[C(x) \ne D(x)]$ is exponentially small, when $x$ is ...
2
votes
1answer
107 views

Approximate-#SAT solver

I am looking for a solver that computes an approximation to #SAT. In other words, given a formula $\phi(x)$ in CNF, approximately count the number of satisfying assignments to $\phi$. I'm interested ...
0
votes
1answer
109 views

Capacity planning algorithm resources

Let's say I have a machine with many boxes of different sizes. I want to put packages inside those boxes. Packages arrive at different time and then stay in the box for specific period of time. I need ...
4
votes
0answers
96 views

Find index set partition that has large projections

I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of ...
16
votes
5answers
1k views

Why economists should care about computational complexity

When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and ...
23
votes
2answers
890 views

Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
7
votes
1answer
251 views

Are there applications of modular graph decomposition in TCS/complexity theory?

What are there some applications of modular graph decomposition in TCS/complexity theory? I am especially interested in its use in proofs or upper/lower bounds if it occurs. [1] Modular graph ...
3
votes
0answers
195 views

Are there applications of experimental mathematics in TCS?

In recent years there have been major, diverse, sometimes surprising advances in experimental mathematics [1] for a variety of sophisticated uses such as developing/deriving exact formulas, theorem ...
7
votes
2answers
216 views

Is there software for graph product calculation and visualization?

I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs. More specifically, I work with labeled, directed multigraphs, and would ...
0
votes
1answer
382 views

How can I prove that Hamming distance is upper bound for Levenshtein distance?

We have a spellchecker software. And one of it crucial parts is hypothesis generator which use Levenshtein distance as a measure of distance between words. The problem with Levenshtein distance is ...
24
votes
4answers
1k views

Ecology and evolution through the algorithmic lens

The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
6
votes
2answers
432 views

Counting number of solutions to a specific SAT formula

I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits ...
1
vote
1answer
247 views

Graph traversal with vertex and edge deadlines/windows

Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph ...
3
votes
3answers
194 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
8
votes
2answers
256 views

Is there any link between TCS and Sustainable Energy research?

Does anybody know of any work that links Theoretical Computer Science and Cheap/Sustainable Energy? i.e is there any work in TCS with the application being in Cheap/Sustainable Energy.
1
vote
0answers
266 views

Encoding a logic in Coq

I want to encode a logic into Coq. The semantics of the logic are very complex and I just want to encode the syntax, axioms, inference rules. I use deep embedding, but I can't use notation like: ...
1
vote
1answer
221 views

Find the best path between two strings

I don't know if CS theory is the best place for this, sorry if it's not. I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on ...
23
votes
4answers
573 views

How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

I am not a computer science theorist, but think this real world problem belongs here. The problem My company have several units accross the country. We offered to employees the possibility to work ...
6
votes
0answers
307 views

Applications of Theoretical Computer Science in Information Theory

Inspired by this question: Information Theory used to prove neat combinatorial statements? Are there any nice applications of theoretical computer science in information theory (the other way has ...
9
votes
1answer
439 views

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

JBV suggested I turn some comments into a question, so here goes. Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". ...
16
votes
5answers
2k views

Real world applications of quantum computing (except for security)

Let's assume that we have built an universal quantum computer. Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it? I am ...
3
votes
1answer
318 views

Approximate bound/algorithm for “product of sums maximization” problem

I am looking for some approximate algorithm with upper/lower bound for the following problem: Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into ...
21
votes
5answers
1k views

Theoretical Applications for Approximation Algorithms

Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm ...
3
votes
3answers
527 views

Maximum-clique practical applications

The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)? All I came with is finding social cliques: ...
8
votes
2answers
353 views

Postselection in geometric complexity theory

Context: As I understand, in geometric complexity theory, the existence of obstructions serves as a proof-certificate, so to speak, for the nonexistence of an efficient computational circuit for the ...
5
votes
1answer
234 views

Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory

I have asked similar questions on stackoverflow; as i couldn't post the very same question in this part of stackexchange. However, i would still like to receive recommendations / advice from this ...
1
vote
1answer
207 views

Does there exist polytime algorithm for this partitioning problem?

I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling ...
9
votes
2answers
908 views

Data structure that allow efficient tag based lookups

I am looking for a highly efficient data structure for storage of data similar to the following. Id Tags Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 ...
1
vote
3answers
186 views

Simple spatial ordering or TSP algorithms?

I'm not sure if this is the right place to ask, but I suppose you'll tell me. I'm writing a program that produces a series of points on a map, and I need to put the points in some linear order so ...
0
votes
3answers
523 views

Practical limits of big-O performance scaling

Lets imagine we have an algorithm made up of a set of operations. Let assume that it has three kind of operations and the time complexity is $t(n) = An + Bn\log n + Cn^2$. This algorithm has ...
1
vote
2answers
428 views

Bin allocation problem

Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway. We have a script as part of an application at work which is responsible ...
4
votes
1answer
130 views

Given a network flow, are there bounds on the change in weight on nodes?

Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight ...
7
votes
2answers
264 views

Is there a local variant of TSP?

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take. It's likely NP-hard, I was just wondering if ...
6
votes
1answer
301 views

Physics and TCS

I was curious as to the ability to move between different academic disciplines with an advanced degree in TCS. So would I be able to move, with a little bit of elbow grease, between physics and ...
2
votes
2answers
297 views

Suggestions on a matching/scheduling algorithm.

I have a problem where mentors need to paired with courses, this is similar to the marriage problem or the hospitals/residents problem except that it isn't. The current solution is terribly written ...
11
votes
1answer
459 views

NP-hardness of a special case of Number Partitioning

Consider the following problem, Given a set of $n = k m$ positive numbers $\{ a_1, \dots, a_n \}$ in which $k \ge 3$ is a constant, we want to partition the set into $m$ subsets of size $k$ so that ...
11
votes
2answers
391 views

Euclidean-squared max-cut in low dimensions

Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
10
votes
1answer
1k views

Minimum path covering problem

We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the ...
15
votes
3answers
442 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
7
votes
6answers
5k views

Application of graph theory in Computer Science

i am a CS student, we did graph theory in class and i found it interesting. i wanted to know what the real applications of graph theory in the computer science field. For an example i found that some ...
11
votes
1answer
239 views

Minimum weight subforest of given cardinality

This question was motivated by a question asked on stackoverflow. Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$). ...
6
votes
2answers
876 views

Applications of computer science in biology

Is there a survey or tutorial article which talks about application of theoretical computer science to emerging fields of applications of computer science in biology, bioinformatics and ...