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
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 ...
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. ...
• 1,786
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$ ...
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 ...
• 2,208
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 ...
• 920
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 ...
• 11k
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 ...
• 12.1k
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 ...
• 11k
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.1k
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, ...
• 31
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 ...
• 11k
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: <...
• 33
1 vote
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 "...
• 111
1 vote
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 ...
1 vote
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 ...
• 11k
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}$..). ...
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 \$...