Questions tagged [application-of-theory]
Questions arising from applications of theoretical computer science in other areas of computer science research/practice or other subjects.
75 questions
4
votes
0
answers
172
views
Has the Moser-Tardos Algorithm Been Applied to Real-World Problems?
I'm studying the Moser-Tardos algorithm, which is often used to efficiently find solutions to satisfiability problems and avoid bad events in probabilistic settings. I’ve read that it’s mainly applied ...
- 388
-1
votes
1
answer
107
views
Representation of binary strings by graphs and hypergraphs
Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$.
Question: Which further ways of representing binary strings of length $...
- 1
1
vote
0
answers
54
views
What are the applications of Belief Revision?
In my Computer Science graduation, I came across this concept of Belief Revision, which focus on knowledge representation and the possible operations that can be done with the facts that a "...
- 111
4
votes
0
answers
95
views
Is the Moser-Tardos algorithm used in any real-world applications?
The Moser-Tardos algorithm can be used to construct algorithms for certain combinatorial problems. However, I'm curious about whether this algorithm is utilized in real-world systems (a SAT solver, ...
- 41
0
votes
1
answer
112
views
What are advantages of bigraphs?
I would like to know if there are any limitations of frameworks such as Petri nets (with its extensions) or pi-calculus that bigraphs developed by Robin Milner do not have.
If there are none, then ...
- 101
16
votes
6
answers
5k
views
Can theoretical computer science be applied in social sciences?
I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my ...
- 369
6
votes
0
answers
127
views
Programmatic higher inductive/inductive-inductive types with equalities between equalities
I can think of practical HITs in verified software that capture some form of alpha equivalence, context equivalence or the example which defines well-typed syntax of type theory from Signatures and ...
- 930
14
votes
0
answers
458
views
What percentage of SODA papers are galactic algorithms?
Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
- 1,901
1
vote
0
answers
96
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 ...
- 19
15
votes
0
answers
363
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 ...
- 331
0
votes
0
answers
68
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}$..). ...
- 1,453
12
votes
2
answers
805
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 ...
- 359
7
votes
4
answers
13k
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 ...
- 243
19
votes
4
answers
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 ...
- 349
-2
votes
2
answers
175
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 ...
- 11.1k
0
votes
1
answer
205
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 ...
- 101
5
votes
0
answers
121
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 ...
- 11.1k
3
votes
0
answers
132
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 ...
- 11.1k
5
votes
1
answer
386
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 ...
- 11.1k
4
votes
2
answers
381
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 ...
- 11.1k
8
votes
0
answers
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$ ...
- 89
2
votes
1
answer
6k
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 ...
- 131
1
vote
0
answers
148
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 ...
- 11.1k
22
votes
3
answers
2k
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. ...
- 10.3k
1
vote
1
answer
1k
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$ ...
- 11.1k
331
votes
29
answers
204k
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 ...
- 7,791
5
votes
0
answers
203
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.4k
11
votes
1
answer
174
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 ...
- 12.4k
4
votes
1
answer
433
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 ...
- 12.4k
0
votes
1
answer
408
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 ...
- 101
4
votes
0
answers
160
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\}$...
- 12.4k
18
votes
5
answers
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 ...
- 10.3k
32
votes
3
answers
3k
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 ...
- 421
8
votes
1
answer
504
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 ...
- 11.1k
5
votes
0
answers
312
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 ...
- 11.1k
8
votes
2
answers
495
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 ...
- 233
-1
votes
2
answers
1k
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 ...
- 117
27
votes
5
answers
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 ...
- 10.3k
6
votes
2
answers
675
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 ...
- 61
2
votes
1
answer
416
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 ...
- 121
3
votes
3
answers
536
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 ...
- 31
9
votes
2
answers
284
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.
- 107
2
votes
0
answers
399
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:
<...
- 33
1
vote
1
answer
255
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 ...
- 123
26
votes
4
answers
752
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 ...
- 363
8
votes
0
answers
914
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 ...
- 2,228
12
votes
1
answer
800
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". ...
- 11.1k
18
votes
5
answers
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 ...
- 635
3
votes
1
answer
433
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 ...
- 463
22
votes
5
answers
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 ...
- 229