# All Questions

11,858 questions
Filter by
Sorted by
Tagged with
22 views

### What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to no it is not being tested

In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the ...
• 101
175 views

### Similarities and differences between Pie and popular languages with dependent types

The book The Little Typer explains dependent types using a toy language called Pie (https://github.com/the-little-typer/pie). How similar is Pie to the popular languages with dependent types: Coq, ...
• 123
44 views

### Ignore side effect in monadic code

Is there a standardized notion of something that removes side effects for an element in a monad? In the case of state monad: An element mx : m X is effectively <...
• 151
79 views

### How exactly does a compatible reduction relation change the $\pi$-calculus?

The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial: It is ...
• 283
56 views

### What data structure for O(1) lookup of multiple keys per value?

I know hash collisions are bad, but are there any hash tables purposefully designed to allow multiples keys per value? Sometimes I want to store something for O(1) lookup where it also has another ...
102 views

• 1,112
60 views

### Models of computation and cardinality [closed]

In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg Essentialy, Pushdown Automata (PA) can solve ...
36 views

• 57
18 views

### Determine number of possible formal languages with a nerode-index of k (k number of equivalence classes)

How can one determine the number of possible formal languages with nerode index of k? For example: How many formal languages are there with a nerode-index of 2? At first i tried to draw the ...
44 views

### Solving sampling problems with circuits?

If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
63 views

• 57
30 views

### Solving K-Flip SAT problem in Polynomial time

Given a dataset with N variables, M clauses in CNF form, and a randomly generated truth assignment T. I am trying to find a truth assignment T' that flips at most k variables and satisfies more ...
60 views

### Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
• 419
1k views

### Are there survey papers in theoretical computer science?

Are there conferences or journals where we can publish surveys/literature review papers related to theoretical computer science problems? If provide a list of such conferences and journals. I know ...
• 83
68 views

### Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al. Are there similar results for ($k$-uniform)...
• 41
76 views

### Reference for complete problems for $FNP^{NP}$

I'm looking for a reference for complete problems for $FNP^{NP}$, i.e., the class of functional problems solvable by a polynomial time non-deterministic Turing machine that has access to an $NP$-...
1 vote
44 views

### CFG - How can I describe a language that dictates a word and its opposite?

I have this question from my Automata class and I am unsure if there's a way to do this. Assuming u,v ∈ {0,1}* and at every character in the word u, the character at the same position in the word v is ...
45 views

### Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures?

Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures? Many of the structures underlying current societies and their governance were designed more than 100 ...
• 2,391
33 views

### Defining a process without internal events

I'm currently working through the book The Prinicples of Protocol Design by Robin Sharp where the reader is introduced to the theory of Communicating Sequential Processes (CSP). The first example ...
42 views

### Perfect simulation of classical dynamical systems

In his paper https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070, David Deutsch defines the perfect simulation of a system S by a computing machine M if there is a program for M that makes M ...
134 views

### For VCP and fixed value k, what's the result if we prove optimal value > (n/2)+(n/k) or we can produce a feasible objective value < (kn)/(k+1)?

I wrote a new idea (by a combination of a well-known SDP formulation and a randomized procedure to conclude that for the Vertex Cover Problem the optimal value > (n/2)+(n/k) or we can produce a ...