Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [application-of-theory]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
83 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 $...
Samdney's user avatar
1 vote
0 answers
44 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 "...
Jonas's user avatar
  • 111
3 votes
0 answers
88 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, ...
Lin's user avatar
  • 31
0 votes
1 answer
108 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 ...
zajer's user avatar
  • 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 ...
wonderinghuh's user avatar
6 votes
0 answers
125 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 ...
Ilk's user avatar
  • 920
14 votes
0 answers
437 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. ...
Laakeri's user avatar
  • 1,786
1 vote
0 answers
95 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 ...
Abdulkader's user avatar
15 votes
0 answers
354 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 ...
WuTheFWasThat's user avatar
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}$..). ...
gradstudent's user avatar
  • 1,453
12 votes
2 answers
783 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 ...
Zur Luria's user avatar
  • 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 ...
user136457's user avatar
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 ...
Rex Butler's user avatar
-2 votes
1 answer
128 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 ...
vzn's user avatar
  • 11k
0 votes
1 answer
204 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 ...
BugShotGG's user avatar
  • 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 ...
vzn's user avatar
  • 11k
3 votes
0 answers
131 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 ...
vzn's user avatar
  • 11k
5 votes
1 answer
366 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 ...
vzn's user avatar
  • 11k
4 votes
2 answers
373 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 ...
vzn's user avatar
  • 11k
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$ ...
Lucas Alves's user avatar
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 ...
fejesjoco's user avatar
  • 131
1 vote
0 answers
145 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 ...
vzn's user avatar
  • 11k
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. ...
Artem Kaznatcheev's user avatar
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$ ...
vzn's user avatar
  • 11k
329 votes
29 answers
203k 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 ...
Manu's user avatar
  • 7,669
5 votes
0 answers
202 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 ...
D.W.'s user avatar
  • 12.1k
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 ...
D.W.'s user avatar
  • 12.1k
4 votes
1 answer
424 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 ...
D.W.'s user avatar
  • 12.1k
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 ...
Jakub Kulhan's user avatar
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\}$...
D.W.'s user avatar
  • 12.1k
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 ...
Artem Kaznatcheev's user avatar
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 ...
Rob Lachlan's user avatar
8 votes
1 answer
497 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 ...
vzn's user avatar
  • 11k
5 votes
0 answers
306 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 ...
vzn's user avatar
  • 11k
8 votes
2 answers
468 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 ...
Rasmus's user avatar
  • 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 ...
Denis Bazhenov's user avatar
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 ...
Artem Kaznatcheev's user avatar
6 votes
2 answers
669 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 ...
Rajeev Kumar's user avatar
2 votes
1 answer
413 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 ...
hDan's user avatar
  • 121
3 votes
3 answers
524 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 ...
brncsk's user avatar
  • 31
8 votes
2 answers
283 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.
NDR's user avatar
  • 97
2 votes
0 answers
392 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: <...
like's user avatar
  • 33
1 vote
1 answer
253 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 ...
amba88's user avatar
  • 123
26 votes
4 answers
750 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 ...
motobói's user avatar
  • 363
8 votes
0 answers
910 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 ...
v s's user avatar
  • 2,208
12 votes
1 answer
768 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". ...
vzn's user avatar
  • 11k
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 ...
Piotr Migdal's user avatar
3 votes
1 answer
431 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 ...
Helium's user avatar
  • 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 ...
Anon1234's user avatar
  • 229
4 votes
3 answers
3k 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: ...
Mixo123's user avatar
  • 41