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

Roman Rabinovich

Roman Rabinovich contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete MathematicsComputer VisionLogic in Computer Sciencemath.COmath.LO

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
5topics
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

3 published item(s)

preprint2020arXiv

CoBe -- Coded Beacons for Localization, Object Tracking, and SLAM Augmentation

This paper presents a novel beacon light coding protocol, which enables fast and accurate identification of the beacons in an image. The protocol is provably robust to a predefined set of detection and decoding errors, and does not require any synchronization between the beacons themselves and the optical sensor. A detailed guide is then given for developing an optical tracking and localization system, which is based on the suggested protocol and readily available hardware. Such a system operates either as a standalone system for recovering the six degrees of freedom of fast moving objects, or integrated with existing SLAM pipelines providing them with error-free and easily identifiable landmarks. Based on this guide, we implemented a low-cost positional tracking system which can run in real-time on an IoT board. We evaluate our system's accuracy and compare it to other popular methods which utilize the same optical hardware, in experiments where the ground truth is known. A companion video containing multiple real-world experiments demonstrates the accuracy, speed, and applicability of the proposed system in a wide range of environments and real-world tasks. Open source code is provided to encourage further development of low-cost localization systems integrating the suggested technology at its navigation core.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

DAG-width is PSPACE-complete

Berwanger et al. show that for every graph $G$ of size $n$ and DAG-width $k$ there is a DAG decomposition of width $k$ and size $n^{O(k)}$. This gives a polynomial time algorithm for determining the DAG-width of a graph for any fixed $k$. However, if the DAG-width of the graphs from a class is not bounded, such algorithms become exponential. This raises the question whether we can always find a DAG decomposition of size polynomial in $n$ as it is the case for tree width and all generalisations of tree width similar to DAG-width. We show that there is an infinite class of graphs such that every DAG decomposition of optimal width has size super-polynomial in $n$ and, moreover, there is no polynomial size DAG decomposition which would approximate an optimal decomposition up to an additive constant. In the second part we use our construction to prove that deciding whether the DAG-width of a given graph is at most a given constant is PSPACE-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rankwidth meets stability

We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs $C$ is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from $C$ using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: - A class of graphs $C$ is a first-order transduction of a class with bounded treewidth if and only if $C$ has bounded rankwidth and a stable edge relation (i.e. graphs from $C$ exclude some half-graph as a semi-induced subgraph). - If a class of graphs $C$ is monadically dependent and not monadically stable, then $C$ has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly $χ$-bounded. Our proofs are effective and lead to polynomial time algorithms.

0 citations0 reviewsNo code linkedOpen access