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.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1 vote
0 answers
146 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
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
-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