domotorp

Budapest, Hungary

http://www.cs.elte.hu/~dom

I work at ELTE, Budapest, in the MTA-ELTE Combinatorial Geometry Research Group. I'm primarily interested in combinatorial geometry, complexity theory and combinatorics.

top accounts reputation activity subscriptions

If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?

mg.metric-geometry algebraic-number-theory discrete-geometry p-adic-numbers asked Jun 10, 2013 at 4:36

mathoverflow.net

45 votes

Can we color Z^+ with n colors such that a, 2a, ..., na all have different colors for all a?

nt.number-theory co.combinatorics open-problem asked May 29, 2010 at 13:41

mathoverflow.net

37 votes

Is there a finite family of functions such that the max of any two functions can be dominated by a third?

co.combinatorics measure-theory asked Nov 10, 2013 at 9:12

mathoverflow.net

34 votes

Does LOGLOG = NLOGLOG?

cc.complexity-theory reference-request space-bounded asked Dec 24, 2010 at 7:47

cstheory.stackexchange.com

31 votes

Is there a natural problem on the naturals that is NP-complete?

cc.complexity-theory np-hardness nt.number-theory combinatorial-game-theory asked Oct 30, 2012 at 15:19

cstheory.stackexchange.com

31 votes

What is simplest polynomial algorithm for PLANARITY?

graph-algorithms co.combinatorics planar-graphs asked Jun 22, 2014 at 10:36

cstheory.stackexchange.com

30 votes

Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

co.combinatorics nt.number-theory graph-theory asked Nov 6, 2012 at 21:14

mathoverflow.net

30 votes

Polynomial with many integer but no other rational solutions?

nt.number-theory polynomials asked May 24, 2021 at 7:09

mathoverflow.net

29 votes

Is there an arbitrarily long arithmetic progression whose members are palindromes?

nt.number-theory palindromes asked May 9, 2015 at 17:28

mathoverflow.net

29 votes

Can we not output the Kolmogorov complexity?

cc.complexity-theory kolmogorov-complexity universal-computation universal-turing-machines asked Apr 26, 2015 at 11:37

cstheory.stackexchange.com

Top Answers

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

cstheory.stackexchange.com

Coloring Planar Graphs

cstheory.stackexchange.com

When does a graph underlie the Hasse diagram of a poset?

mathoverflow.net

Can any sequence of consecutive integers be realized as winding numbers?

mathoverflow.net

Does every polyomino tile R^n for some n?

mathoverflow.net

PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?

cstheory.stackexchange.com

Is the ratio Perimeter/Area for a finite union of unit squares at most 4?

mathoverflow.net

Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

cstheory.stackexchange.com

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

cstheory.stackexchange.com

Comparing Two Algorithms for 3SUM problem over Integers

cstheory.stackexchange.com

Why do computer scientists on the whole work under the assumption that P ≠ NP?

cstheory.stackexchange.com

What computational problems would be good proof-of-work problems for cryptocurrency mining?

mathoverflow.net

Is the wording of Google's QC Supremacy valid?

cstheory.stackexchange.com

"Advice to young mathematicians"

math.stackexchange.com

Straight line complexity of monomials

cstheory.stackexchange.com

Minimizing the excursion of a sum of unit vectors

mathoverflow.net

Find Shortest Pairwise Distance of Points in o(n log n)?

cstheory.stackexchange.com

How many tacks fit in the plane?

mathoverflow.net

Positive topological ordering, take 3

cstheory.stackexchange.com

Why is the population of post-Soviet states declining?

politics.stackexchange.com

Circuit lower bounds and kolmogorov complexity

cstheory.stackexchange.com

Bi-partitioning $2n$ points on the plane with a straight line

mathoverflow.net

The number of relevant scales for a finite metric space

mathoverflow.net

Protocol partition number and deterministic communication complexity

cstheory.stackexchange.com

The "sensitivity" of 2-colorings of the d-dimensional integer lattice

mathoverflow.net

Dyck paths on rectangles

mathoverflow.net

Expected values of Kolmogorov complexity in a random sample

cstheory.stackexchange.com

Is this kind of "Gerrymandering" NP-complete?

mathoverflow.net

Is there always a maximum anti-rectangle with a corner square?

mathoverflow.net

Covering a (hyper)cube with lines

mathoverflow.net