BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Márton Naszódi

Márton Naszódi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.MGmath.COData Structures and Algorithmsmath.FA

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2021arXiv

Computing the covering radius of a polytope with an application to lonely runners

We are concerned with the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximation of the average of some random matrices

Rudelson's theorem states that if for a set of unit vectors $u_i$ and positive weights $c_i$, we have that $\sum c_i u_i\otimes u_i$ is the identity operator $I$ on ${\mathbb R}^d$, then the sum of a random sample of $Cd\ln d$ of these diadic products is close to $I$. The $\ln d$ term cannot be removed. On the other hand, the recent fundamental result of Batson, Spielman and Srivastava and its improvement by Marcus, Spielman and Srivastava show that the $\ln d$ term can be removed, if one wants to show the existence of a good approximation of $I$ as the average of a few diadic products. It is known that essentially the same proof as Rudelson's yields a more general statement about the average of positive semi-definite matrices. First, we give an example of an average of positive semi-definite matrices where there is no approximation of this average by $Cd$ elements. Thus, the result of Batson, Spielman and Srivastava cannot be extended to this wider class of matrices. Next, we present a stability version of Rudelson's result on positive semi-definite matrices, and thus, extend it to certain non-symmetric matrices. This yields applications to the study of the Banach--Mazur distance of convex bodies. Finally, we show that in some cases, one needs to take a subset of the vectors of order $d^2$ to approximate the identity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Colorful Helly-type Theorems for the Volume of Intersections of Convex Bodies

We prove the following Helly-type result. Let $\mathcal{C}_1,\dots,\mathcal{C}_{3d}$ be finite families of convex bodies in $\mathbb{R}^d$. Assume that for any colorful selection of $2d$ sets, $C_{i_k}\in \mathcal{C}_{i_k}$ for each $1\leq k\leq 2d$ with $1\leq i_1<\dots<i_{2d}\leq 3d$, the intersection $\bigcap\limits_{k=1}^{2d} C_{i_k}$ is of volume at least 1. Then there is an $1\leq i \leq 3d$ such that $\bigcap\limits_{C\in \mathcal{C}_i} C$ is of volume at least $d^{-O(d^2)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Arrangements of homothets of a convex body II

A family of homothets of an o-symmetric convex body K in d-dimensional Euclidean space is called a Minkowski arrangement if no homothet contains the center of any other homothet in its interior. We show that any pairwise intersecting Minkowski arrangement of a d-dimensional convex body has at most $2\cdot 3^d$ members. This improves a result of Polyanskii (arXiv:1610.04400). Using similar ideas, we also give a proof the following result of Polyanskii: Let $K_1,\dots,K_n$ be a sequence of homothets of the o-symmetric convex body $K$, such that for any $i<j$, the center of $K_j$ lies on the boundary of $K_i$. Then $n\leq O(3^d d)$.

0 citations0 reviewsNo code linkedOpen access