Questions arising from applications of theoretical computer science in other areas of computer science research/practice or other subjects.
4
votes
0answers
42 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 ...
15
votes
4answers
664 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 ...
22
votes
2answers
647 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 ...
0
votes
0answers
170 views
Hypergraph decompositions used in TCS?
I am looking for general or notable theory and applications of hypergraph decompositions in TCS. For example:
there is a modular graph decomposition [1]. Has it or anything like it been extended to ...
6
votes
1answer
172 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 ...
4
votes
0answers
173 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
183 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
266 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 ...
22
votes
3answers
829 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
418 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
172 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
128 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
253 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
237 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
215 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 ...
21
votes
4answers
513 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 departments accross the country.
We offered to employees the possibility to ...
5
votes
0answers
203 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 ...
7
votes
1answer
383 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 ...
2
votes
1answer
244 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
901 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
346 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: ...
7
votes
2answers
325 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 ...
4
votes
1answer
204 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
199 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 ...
0
votes
0answers
154 views
is Language regular ? [closed]
Is this Language regular ?
L = {w ∈ Σ {Y, N}* : w contains at least two Y’s and at most two N’s}
My thinking way :
using pumping lemma I took w = uvw / uv = (Y)^n(N)^n (this case happen if only n = ...
9
votes
2answers
614 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
152 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
488 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
384 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
121 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 ...
6
votes
2answers
249 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
287 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
224 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
383 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
363 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
959 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
408 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 - ...
5
votes
6answers
4k 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
225 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$).
...
5
votes
2answers
705 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 ...
4
votes
2answers
173 views
Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)
In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy ...
16
votes
4answers
392 views
Is there current research into the implemention of Randomness Extractors?
Has there been research into implementing randomness extractor constructions?
It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
6
votes
1answer
337 views
Is that particular case of the “minimum weight solution to linear equations” still NP-complete?
We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find ...
3
votes
3answers
296 views
Is Degrees Of Separation NP Complete?
I'm doing a bit of research on doing social analysis between so called "hub" people. Basically what I want to try to do is determine the shortest paths between two individuals. The problem is that ...
11
votes
3answers
649 views
What are some examples of secret sharing schemes actually being used in real-world applications?
The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, ...
8
votes
11answers
1k views
What are some real world applications for genetic algorithms?
What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?
