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

Robert Schweller

Robert Schweller contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Emerging TechnologiesComputational ComplexityComputational GeometryCryptography and Security

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
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

3 published item(s)

preprint2020arXiv

Covert Computation in Self-Assembled Circuits

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography. In this paper we propose the problem of performing ``covert computation'' within tile self-assembly that seeks to design self-assembly systems that ``conceal'' both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract Tile Assembly Model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions

Motivated by advances is nanoscale applications and simplistic robot agents, we look at problems based on using a global signal to move all agents when given a limited number of directional signals and immovable geometry. We study a model where unit square particles move within a 2D grid based on uniform external forces. Movement is based on a sequence of uniform commands which cause all particles to move 1 step in a specific direction. The 2D grid board additionally contains "blocked" spaces which prevent particles from entry. Within this model, we investigate the complexity of deciding 1) whether a target location on the board can be occupied (by any) particle (\emph{occupancy problem}), 2) whether a specific particle can be relocated to another specific position in the board (\emph{relocation problem}), and 3) whether a board configuration can be transformed into another configuration (\emph{reconfiguration problem}). We prove that while occupancy is solvable in polynomial time, the relocation and reconfiguration problems are both NP-Complete even when restricted to only 2 or 3 movement directions. We further define a hierarchy of board geometries and show that this hardness holds for even very restricted classes of board geometry.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Algorithms for Testing Monomials in Multivariate Polynomials

This paper is our second step towards developing a theory of testing monomials in multivariate polynomials. The central question is to ask whether a polynomial represented by an arithmetic circuit has some types of monomials in its sum-product expansion. The complexity aspects of this problem and its variants have been investigated in our first paper by Chen and Fu (2010), laying a foundation for further study. In this paper, we present two pairs of algorithms. First, we prove that there is a randomized $O^*(p^k)$ time algorithm for testing $p$-monomials in an $n$-variate polynomial of degree $k$ represented by an arithmetic circuit, while a deterministic $O^*(6.4^k + p^k)$ time algorithm is devised when the circuit is a formula, here $p$ is a given prime number. Second, we present a deterministic $O^*(2^k)$ time algorithm for testing multilinear monomials in $Π_mΣ_2Π_t\times Π_kΠ_3$ polynomials, while a randomized $O^*(1.5^k)$ algorithm is given for these polynomials. The first algorithm extends the recent work by Koutis (2008) and Williams (2009) on testing multilinear monomials. Group algebra is exploited in the algorithm designs, in corporation with the randomized polynomial identity testing over a finite field by Agrawal and Biswas (2003), the deterministic noncommunicative polynomial identity testing by Raz and Shpilka (2005) and the perfect hashing functions by Chen {\em at el.} (2007). Finally, we prove that testing some special types of multilinear monomial is W[1]-hard, giving evidence that testing for specific monomials is not fixed-parameter tractable.

0 citations0 reviewsNo code linkedOpen access