User domotorp

3 votes

Accepted

How hard is it to determine the chromatic number of a unit distance graph?

answered May 18, 2018 at 7:57

2 votes

Accepted

How to generalize VC dimension?

answered Mar 7, 2019 at 22:17

2 votes

Accepted

$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

answered Mar 21, 2019 at 22:25

2 votes

Accepted

Planar Exact Cover by even-size sets

answered Jun 30, 2019 at 20:14

2 votes

A subset grouping problem

answered Feb 12, 2017 at 22:02

2 votes

Accepted

Complexity involving connected components of 0/1 matrix

answered Sep 27, 2016 at 20:43

2 votes

Accepted

Does every NO instance of this promise problem have a local refutation?

answered Nov 20, 2016 at 14:44

2 votes

Problems still "hard" in the SMP/Referee model with shared randomness?

answered Mar 4, 2016 at 18:38

2 votes

Is a theoretically secure key exchange possible?

answered Aug 30, 2016 at 20:15

2 votes

NP-hardness of a planar SAT variant

answered Oct 28, 2019 at 5:45

2 votes

If $P=BPP$, then Is it correct that $IP=NP$?

answered Nov 19, 2019 at 17:09

2 votes

Accepted

find the most similar topological ordering of a dag

answered Jul 30, 2020 at 10:32

2 votes

Accepted

Check whether DFA accepts majority of words less than a cutoff with another DFA

answered Oct 8, 2022 at 20:51

2 votes

Accepted

Communication complexity of graph isomorphism with 2-sided error

answered Oct 17 at 11:16

2 votes

Bounds on the size of the smallest NFA for L_k-distinct

answered Mar 23, 2014 at 16:52

2 votes

What is the minimum size of a circuit that computes PARITY?

answered Oct 20, 2014 at 12:47

2 votes

Computing parity of a permutation in a streaming-fashion way

answered Dec 21, 2014 at 8:15

2 votes

Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

answered Apr 18, 2013 at 17:17

2 votes

Accepted

Dividing users with certain files into 2 equal groups

answered Nov 24, 2013 at 9:50

2 votes

Nonregular Languages in Sublogarithmic Space

answered Nov 30, 2013 at 21:14

2 votes

Complexity of universal computation on random input

answered Jul 7, 2012 at 6:24

1 vote

Reducing space usage of st-connectivity with multiple passes?

answered Nov 5, 2011 at 7:21

1 vote

How many DFAs accept two given strings?

answered Jul 30, 2011 at 17:50

1 vote

Naming the Boxes

answered Jan 10, 2011 at 8:22

1 vote

Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

answered Jan 21, 2011 at 8:21

1 vote

Network Flow with Non-contiguous Capacities

answered Nov 19, 2013 at 20:03

1 vote

Accepted

On the proof of Meyer's Theorem

answered May 16, 2013 at 19:09

1 vote

Accepted

Find all hyperplanes separating unique sets of `k` points

answered Jun 11, 2014 at 17:42

1 vote

Communication complexity of equality on graphs

answered Mar 25, 2023 at 5:35

1 vote

Is there a fundamental link between Nash's equilibrium and Turing's halting problem?

answered Sep 21, 2021 at 18:55

Stack Exchange Network

133 Answers

How hard is it to determine the chromatic number of a unit distance graph?

How to generalize VC dimension?

$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?

Planar Exact Cover by even-size sets

A subset grouping problem

Complexity involving connected components of 0/1 matrix

Does every NO instance of this promise problem have a local refutation?

Problems still "hard" in the SMP/Referee model with shared randomness?

Is a theoretically secure key exchange possible?

NP-hardness of a planar SAT variant

If $P=BPP$, then Is it correct that $IP=NP$?

find the most similar topological ordering of a dag

Check whether DFA accepts majority of words less than a cutoff with another DFA

Communication complexity of graph isomorphism with 2-sided error

Bounds on the size of the smallest NFA for L_k-distinct

What is the minimum size of a circuit that computes PARITY?

Computing parity of a permutation in a streaming-fashion way

Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

Dividing users with certain files into 2 equal groups

Nonregular Languages in Sublogarithmic Space

Complexity of universal computation on random input

Reducing space usage of st-connectivity with multiple passes?

How many DFAs accept two given strings?

Naming the Boxes

Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

Network Flow with Non-contiguous Capacities

On the proof of Meyer's Theorem

Find all hyperplanes separating unique sets of `k` points

Communication complexity of equality on graphs

Is there a fundamental link between Nash's equilibrium and Turing's halting problem?