We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [application-of-theory]

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

67 questions
Filter by
Sorted by
Tagged with
1k 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$ ...
79 views

### Impartial Combinatorial Games as a core of the final undergraduate project

Solving several problems of Impartial Combinatorial Games in Game Theory has drawn my attention. So that, I'd like to ask if it's possible to use this topic (e.g. Sprague Grundy theorem) as a core or ...
598 views

### Are social networks typically good expanders?

I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility ...
233 views

### Differential privacy and data poisoning

A differentially private algorithm takes datasets containing inputs and produces randomized outputs, such that no small change in the dataset can shift the distribution of outputs by too much. This ...
20k views

### Application of graph theory in computer science

I am a CS student. We did graph theory in one course. I found it interesting. What are the real applications of graph theory in the computer science field? For example, I found that some concepts ...
62 views

### Iterative algorithms and Lyapunov functions

Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). ...
8k views

### Applications of Hamiltonian Cycle Problem

The Hamiltonian Cycle Problem and Travelling Salesman Problem are among famous NP-complete problems and has been studied extensively. I am looking for applications of the HamCycle and TSP. What are ...
192 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 ...
5k 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?
3k views

### Math talk: Theorem about git revision control system?

I would like to give a mathematics talk on the git revision control system. It is now widely used in mathematics as well as in the computer science industry. For example, the HoTT (Homotopy Type ...
107 views

### what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of ...
962 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 ...
177 views

### How to map random cardesian points in a 2d array

I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given N random ...
2k 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 ...
117 views

### extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
110 views

### minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
226 views

### any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big ...
2k 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 ...
350 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 ...
4k 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 ...
120 views

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

a recent difficult question of interest to the group by GB has possibly led to verification of a new graph property by dspyz, by use of Answer Set Programming/ASP. via sophisticated logic ...
1k 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. ...
416 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$ ...
708 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 ...
193k 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 ...
149 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 drawn ...
331 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 ...
281 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 ...
2k 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 ...
152 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 $\{1,2,\dots,n\}$...
447 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.  Modular graph ...
3k 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 ...
334 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 ...
277 views

### Are there applications of experimental mathematics in TCS?

In recent years there have been major, diverse, sometimes surprising advances in experimental mathematics  for a variety of sophisticated uses such as developing/deriving exact formulas, theorem ...
241 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 ...
379 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 ...
525 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 ...
371 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 ...
336 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: <...
271 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.
562 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  asks about applications of QM computing. One answer  was "efficiently simulating quantum mechanics". ...
826 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 ...
2k 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 ...
565 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 ...
393 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 disjoint ...
2k 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: ...
407 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 ...
275 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 ...