User domotorp

4 votes

Does XOR automata (NXA) for finite languages benefit from cycles?

answered Oct 3, 2014 at 20:05

4 votes

On the notion of positive rank

answered Jan 27, 2015 at 21:47

4 votes

Asymptotic complexity of sorting using k-comparisons

answered Jun 9, 2013 at 19:16

4 votes

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

answered Sep 16, 2013 at 14:00

4 votes

How do I construct an optimal affix code?

answered Jan 6, 2013 at 12:57

4 votes

Subset Numbering

answered Jul 25, 2012 at 8:23

4 votes

How hard is Mafia?

answered Oct 31, 2012 at 8:17

4 votes

Binary search generalizations for posets?

answered Nov 11, 2011 at 10:55

3 votes

Permutation game redux

answered Dec 30, 2011 at 11:58

3 votes

Commonest Subsequence

answered Aug 26, 2012 at 7:40

3 votes

Accepted

complexity of games with just doors and keys

answered Jan 19, 2013 at 9:51

3 votes

Good seating arrangements for sequence of meals and tables of size k for a group of people

answered Feb 18, 2013 at 13:14

3 votes

One way randomised communication complexity of disjointness

answered Jan 21, 2011 at 17:09

3 votes

Complexity of counting when there is no parsimonious reduction

answered Apr 17, 2011 at 12:49

3 votes

Accepted

Is set packing easier when the sets are squares?

answered Dec 23, 2013 at 21:16

3 votes

Kruskal-Katona Theorem with Majority?

answered Nov 22, 2013 at 9:59

3 votes

Multi prover, verifier games and PCP theorem

answered Jul 13, 2013 at 8:00

3 votes

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

answered May 28, 2013 at 7:46

3 votes

Accepted

Communication complexity of Independent Set game?

answered Mar 31, 2015 at 22:55

3 votes

Representation as sum of unit fractions: primitive recursive?

answered Jan 3, 2015 at 22:43

3 votes

Accepted

Combining subset sum and subset product problems

answered Jan 12, 2014 at 18:40

3 votes

List of nice non-context-free languages

answered Mar 8 at 8:13

3 votes

We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q?

answered May 6, 2020 at 6:37

3 votes

Coloring where all colors are present in closed neighborhood of every vertex

answered Nov 13, 2020 at 8:22

3 votes

Is the transducer version of BPP closed under complement?

answered Dec 5, 2019 at 19:50

3 votes

Is the transducer version of BPP closed under complement?

answered Dec 6, 2019 at 8:35

3 votes

Accepted

Directed graph with bounded in-deg can be partitioned in a balanced way

answered Aug 6, 2017 at 12:03

3 votes

Accepted

Compression algorithms for low-complexity strings?

answered Jan 19, 2017 at 9:21

3 votes

How much memory is needed for counting distinct elements in a stream exactly with high probability

answered Feb 7, 2017 at 21:48

3 votes

Base-k representations of the co-domain of a polynomial - is it context-free?

answered Nov 18, 2018 at 21:27

Stack Exchange Network

133 Answers

Does XOR automata (NXA) for finite languages benefit from cycles?

On the notion of positive rank

Asymptotic complexity of sorting using k-comparisons

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

How do I construct an optimal affix code?

Subset Numbering

How hard is Mafia?

Binary search generalizations for posets?

Permutation game redux

Commonest Subsequence

complexity of games with just doors and keys

Good seating arrangements for sequence of meals and tables of size k for a group of people

One way randomised communication complexity of disjointness

Complexity of counting when there is no parsimonious reduction

Is set packing easier when the sets are squares?

Kruskal-Katona Theorem with Majority?

Multi prover, verifier games and PCP theorem

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

Communication complexity of Independent Set game?

Representation as sum of unit fractions: primitive recursive?

Combining subset sum and subset product problems

List of nice non-context-free languages

We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q?

Coloring where all colors are present in closed neighborhood of every vertex

Is the transducer version of BPP closed under complement?

Is the transducer version of BPP closed under complement?

Directed graph with bounded in-deg can be partitioned in a balanced way

Compression algorithms for low-complexity strings?

How much memory is needed for counting distinct elements in a stream exactly with high probability

Base-k representations of the co-domain of a polynomial - is it context-free?