Showing 1–13 of 13 results for author: Pajak, D

Parameter Blending for Multi-Camera Harmonization for Automotive Surround View Systems

Authors: Yuzhuo Ren, Yining Deng, David Pajak, Robin Jenkin, Niranjan Avadhanam, Varsha Hedau

Abstract: In a surround view system, the image color and tone captured by multiple cameras can be different due to cameras applying auto white balance (AWB), global tone mapping (GTM) individually for each camera. The color and brightness along stitched seam location may look discontinuous among multiple cameras which impacts overall stitched image visual quality. To improve the color transition between adj… ▽ More In a surround view system, the image color and tone captured by multiple cameras can be different due to cameras applying auto white balance (AWB), global tone mapping (GTM) individually for each camera. The color and brightness along stitched seam location may look discontinuous among multiple cameras which impacts overall stitched image visual quality. To improve the color transition between adjacent cameras in stitching algorithm, we propose harmonization algorithm which applies before stitching to adjust multiple cameras' color and tone so that stitched image has smoother color and tone transition between adjacent cameras. Our proposed harmonization algorithm consists of AWB harmonization and GTM harmonization leveraging Image Signal Processor (ISP)'s AWB and GTM metadata statistics. Experiment result shows that our proposed algorithm outperforms global color transfer method in both visual quality and computational cost. △ Less

Submitted 16 June, 2024; originally announced June 2024.

Efficient Algorithm for Deterministic Search of Hot Elements

Authors: Dariusz R. Kowalski, Dominik Pajak

Abstract: When facing a very large stream of data, it is often desirable to extract most important statistics online in a short time and using small memory. For example, one may want to quickly find the most influential users generating posts online or check if the stream contains many identical elements. In this paper, we study streams containing insertions and deletions of elements from a possibly large s… ▽ More When facing a very large stream of data, it is often desirable to extract most important statistics online in a short time and using small memory. For example, one may want to quickly find the most influential users generating posts online or check if the stream contains many identical elements. In this paper, we study streams containing insertions and deletions of elements from a possibly large set $N$ of size $|N| = n$, that are being processed by online deterministic algorithms. At any point in the stream the algorithm may be queried to output elements of certain frequency in the already processed stream. More precisely, the most frequent elements in the stream so far. The output is considered correct if the returned elements it contains all elements with frequency greater than a given parameter $\varphi$ and no element with frequency smaller than $\varphi-ε$. We present an efficient online deterministic algorithm for solving this problem using $O(\min(n, \frac{polylog(n)}ε))$ memory and $O(polylog(n))$ time per processing and outputting an element. It is the first such algorithm as the previous algorithms were either randomized, or processed elements in substantially larger time $Ω(\min(n, \frac{\log n}ε))$, or handled only insertions and required two passes over the stream (i.e., were not truly online). Our solution is almost-optimally scalable (with only a polylogarithmic overhead) and does not require randomness or scanning twice through the stream. We complement the algorithm analysis with a lower bound $Ω(\min(n, \frac{1}ε))$ on required memory. △ Less

Submitted 28 March, 2022; originally announced March 2022.

Tree exploration in dual-memory model

Authors: Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, Dominik Pajak

Abstract: We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering to a node, do not receive as input the edge via which they entered. In such a model, deterministic memoryless exploration is infeasible, hence the age… ▽ More We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering to a node, do not receive as input the edge via which they entered. In such a model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic at each node is possible in linear time when one of two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then exploration may require quadratic time on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear exploration of trees in the model with two types of memory, but having neither of those features may lead to quadratic exploration time even on a simple path. △ Less

Submitted 26 December, 2021; originally announced December 2021.

Efficient Deterministic Quantitative Group Testing for Precise Information Retrieval

Authors: Dariusz R. Kowalski, Dominik Pajak

Abstract: The Quantitative Group Testing (QGT) is about learning a (hidden) subset $K$ of some large domain $N$ using a sequence of queries, where a result of a query provides information about the size of the intersection of the query with the unknown subset $K$. Almost all previous work focused on randomized algorithms minimizing the number of queries; however, in case of large domains $N$, randomization… ▽ More The Quantitative Group Testing (QGT) is about learning a (hidden) subset $K$ of some large domain $N$ using a sequence of queries, where a result of a query provides information about the size of the intersection of the query with the unknown subset $K$. Almost all previous work focused on randomized algorithms minimizing the number of queries; however, in case of large domains $N$, randomization may result in a significant deviation from the expected precision. Others assumed unlimited computational power (existential results) or adaptiveness of queries. In this work we propose efficient non-adaptive deterministic QGT algorithms for constructing queries and deconstructing a hidden set $K$ from the results of the queries, without using randomization, adaptiveness or unlimited computational power. The efficiency is three-fold. First, in terms of almost-optimal number of queries - we improve it by factor nearly $|K|$ comparing to previous constructive results. Second, our algorithms construct the queries and reconstruct set $K$ in polynomial time. Third, they work for any hidden set $K$, as well as multi-sets, and even if the results of the queries are capped at $\sqrt{|K|}$. We also analyze how often elements occur in queries and its impact to parallelization and fault-tolerance of the query system. △ Less

Submitted 20 April, 2022; v1 submitted 4 December, 2021; originally announced December 2021.

Generalized Framework for Group Testing: Queries, Feedbacks and Adversaries

Authors: Marek Klonowski, Dariusz R. Kowalski, Dominik Pajak

Abstract: In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersection between the query and subset K. Several specific feedbacks have been studied in the literature, often proving different formulas for the estimate of the query complexity of the prob… ▽ More In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersection between the query and subset K. Several specific feedbacks have been studied in the literature, often proving different formulas for the estimate of the query complexity of the problem, defined as the shortest length of queries' sequence solving Group Testing problem with specific feedback. In this paper we study what are the properties of the feedback that influence the query complexity of Group Testing and what is their measurable impact. We propose a generic framework that covers a vast majority of relevant settings considered in the literature, which depends on two fundamental parameters of the feedback: input capacity $α$ and output expressiveness $β$. They upper bound the logarithm of the size of the feedback function domain and image, respectively. To justify the value of the framework, we prove upper bounds on query complexity of non adaptive, deterministic Group Testing under some "efficient" feedbacks, for minimum, maximum and general expressiveness, and complement them with a lower bound on all feedbacks with given parameters $α,β$. Our upper bounds also hold if the feedback function could get an input twisted by a malicious adversary, in case the intersection of a query and the hidden set is bigger than the feedback capacity $α$. We also show that slight change in the feedback function may result in substantial worsening of the query complexity. Additionally, we analyze explicitly constructed randomized counterparts of the deterministic results. Our results provide some insights to what are the most useful bits of information an output-restricted feedback could provide, and open a number of challenging research directions. △ Less

Submitted 2 December, 2021; originally announced December 2021.

Widening Access to Applied Machine Learning with TinyML

Authors: Vijay Janapa Reddi, Brian Plancher, Susan Kennedy, Laurence Moroney, Pete Warden, Anant Agarwal, Colby Banbury, Massimo Banzi, Matthew Bennett, Benjamin Brown, Sharad Chitlangia, Radhika Ghosal, Sarah Grafman, Rupert Jaeger, Srivatsan Krishnan, Maximilian Lam, Daniel Leiker, Cara Mann, Mark Mazumder, Dominic Pajak, Dhilan Ramaprasad, J. Evan Smith, Matthew Stewart, Dustin Tingley

Abstract: Broadening access to both computational and educational resources is critical to diffusing machine-learning (ML) innovation. However, today, most ML resources and experts are siloed in a few countries and organizations. In this paper, we describe our pedagogical approach to increasing access to applied ML through a massive open online course (MOOC) on Tiny Machine Learning (TinyML). We suggest tha… ▽ More Broadening access to both computational and educational resources is critical to diffusing machine-learning (ML) innovation. However, today, most ML resources and experts are siloed in a few countries and organizations. In this paper, we describe our pedagogical approach to increasing access to applied ML through a massive open online course (MOOC) on Tiny Machine Learning (TinyML). We suggest that TinyML, ML on resource-constrained embedded devices, is an attractive means to widen access because TinyML both leverages low-cost and globally accessible hardware, and encourages the development of complete, self-contained applications, from data collection to deployment. To this end, a collaboration between academia (Harvard University) and industry (Google) produced a four-part MOOC that provides application-oriented instruction on how to develop solutions using TinyML. The series is openly available on the edX MOOC platform, has no prerequisites beyond basic programming, and is designed for learners from a global variety of backgrounds. It introduces pupils to real-world applications, ML algorithms, data-set engineering, and the ethical considerations of these technologies via hands-on programming and deployment of TinyML applications in both the cloud and their own microcontrollers. To facilitate continued learning, community building, and collaboration beyond the courses, we launched a standalone website, a forum, a chat, and an optional course-project competition. We also released the course materials publicly, hoping they will inspire the next generation of ML practitioners and educators and further broaden access to cutting-edge ML technologies. △ Less

Submitted 9 June, 2021; v1 submitted 7 June, 2021; originally announced June 2021.

Comments: Understanding the underpinnings of the TinyML edX course series: https://www.edx.org/professional-certificate/harvardx-tiny-machine-learning

Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

Authors: Frederik Mallmann-Trenn, Yannic Maus, Dominik Pajak

Abstract: We study a process of \emph{averaging} in a distributed system with \emph{noisy communication}. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local… ▽ More We study a process of \emph{averaging} in a distributed system with \emph{noisy communication}. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value $v$, the receiving agent receives $v+N$, where $N$ is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares $TSS(t)$, which measures the sum of square distances from the average load to the \emph{initial average} and (ii) $\barφ(t)$, measures the sum of square distances from the average load to the \emph{running average} (average at time $t$). It is known that the simple averaging protocol---in which an agent sends its current value and sets its new value to the average of the received value and its current value---converges eventually to a state where $\barφ(t)$ is small. It has been observed that $TSS(t)$, due to the noise, eventually diverges and previous research---mostly in control theory---has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of $\barφ(t)$ and precise bounds on the drift of $TSS(t)$ that show that albeit $TSS(t)$ eventually diverges, for a wide and interesting range of parameters, $TSS(t)$ stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding. △ Less

Submitted 24 April, 2019; originally announced April 2019.

Self-Stabilizing Task Allocation In Spite of Noise

Authors: Anna Dornhaus, Nancy Lynch, Frederik Mallmann-Trenn, Dominik Pajak, Tsvetomira Radeva

Abstract: We study the problem of distributed task allocation inspired by the behavior of social insects, which perform task allocation in a setting of limited capabilities and noisy environment feedback. We assume that each task has a demand that should be satisfied but not exceeded, i.e., there is an optimal number of ants that should be working on this task at a given time. The goal is to assign a near-o… ▽ More We study the problem of distributed task allocation inspired by the behavior of social insects, which perform task allocation in a setting of limited capabilities and noisy environment feedback. We assume that each task has a demand that should be satisfied but not exceeded, i.e., there is an optimal number of ants that should be working on this task at a given time. The goal is to assign a near-optimal number of workers to each task in a distributed manner and without explicit access to the values of the demands nor the number of ants working on the task. We seek to answer the question of how the quality of task allocation depends on the accuracy of assessing whether too many (overload) or not enough (lack) ants are currently working on a given task. Concretely, we address the open question of solving task allocation in the model where each ant receives feedback that depends on the deficit defined as the (possibly negative) difference between the optimal demand and the current number of workers in the task. The feedback is modeled as a random variable that takes value lack or overload with probability given by a sigmoid of the deficit. Each ants receives the feedback independently, but the higher the overload or lack of workers for a task, the more likely it is that all the ants will receive the same, correct feedback from this task; the closer the deficit is to zero, the less reliable the feedback becomes. We measure the performance of task allocation algorithms using the notion of regret, defined as the absolute value of the deficit summed over all tasks and summed over time. We propose a simple, constant-memory, self-stabilizing, distributed algorithm that quickly converges from any initial distribution to a near-optimal assignment. We also show that our algorithm works not only under stochastic noise but also in an adversarial noise setting. △ Less

Submitted 12 May, 2018; v1 submitted 9 May, 2018; originally announced May 2018.

On Simple Back-Off in Unreliable Radio Networks

Authors: Seth Gilbert, Nancy Lynch, Calvin Newport, Dominik Pajak

Abstract: In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic comm… ▽ More In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with a preliminary investigation of the performance of these strategies when we include additional generality to the model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks. △ Less

Submitted 15 December, 2018; v1 submitted 6 March, 2018; originally announced March 2018.

Broadcast in radio networks: time vs. energy tradeoffs

Authors: Marek Klonowski, Dominik Pająk

Abstract: In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting and receiving messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions by a single station. The goal of… ▽ More In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting and receiving messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions by a single station. The goal of the paper is to study tradeoffs between time and energy complexity of broadcast problem in multi-hop radio networks. We consider a model where the topology of the network is unknown and if two neighbors of a station are transmitting in the same discrete time slot, then the signals collide and the receiver cannot distinguish the collided signals from silence. We observe that existing, time efficient, algorithms are not optimized with respect to energy expenditure. We then propose and analyse two new randomized energy-efficient algorithms. Our first algorithm works in time $O((D+\varphi)\cdot n^{1/\varphi}\cdot \varphi)$ with high probability and uses $O(\varphi)$ energy per station for any $\varphi \leq \log n/(2\log\log n)$ for any graph with $n$ nodes and diameter $D$. Our second algorithm works in time $O((D+\log n)\log n)$ with high probability and uses $O(\log n/\log\log n)$ energy. We prove that our algorithms are almost time-optimal for given energy limits for graphs with constant diameters by constructing lower bound on time of $Ω(n^{1/\varphi} \cdot \varphi)$. The lower bound shows also that any algorithm working in polylogaritmic time in $n$ for all graphs needs energy $Ω(\log n/\log\log n)$. △ Less

Submitted 13 May, 2018; v1 submitted 11 November, 2017; originally announced November 2017.

On Location Hiding in Distributed Systems

Authors: Karol Gotfryd, Marek Klonowski, Dominik Pająk

Abstract: We consider the following problem - a group of mobile agents perform some task on a terrain modeled as a graph. In a given moment of time an adversary gets an access to the graph and positions of the agents. Shortly before adversary's observation the mobile agents have a chance to relocate themselves in order to hide their initial configuration. We assume that the initial configuration may possibl… ▽ More We consider the following problem - a group of mobile agents perform some task on a terrain modeled as a graph. In a given moment of time an adversary gets an access to the graph and positions of the agents. Shortly before adversary's observation the mobile agents have a chance to relocate themselves in order to hide their initial configuration. We assume that the initial configuration may possibly reveal to the adversary some information about the task they performed. Clearly agents have to change their location in possibly short time using minimal energy. In our paper we introduce a definition of a \emph{well hiding} algorithm in which the starting and final configurations of the agents have small mutual information. Then we discuss the influence of various features of the model on the running time of the optimal well-hiding algorithm. We show that if the topology of the graph is known to the agents, then the number of steps proportional to the diameter of the graph is sufficient and necessary. In the unknown topology scenario we only consider a single agent case. We first show that the task is impossible in the deterministic case if the agent has no memory. Then we present a polynomial randomized algorithm. Finally in the model with memory we show that the number of steps proportional to the number of edges of the graph is sufficient and necessary. In some sense we investigate how complex is the problem of "losing" information about location (both physical and logical) for different settings. △ Less

Submitted 13 November, 2016; originally announced November 2016.

Comments: Submitted to 10th International Conference on Algorithms and Complexity CIAC 2017

Time and space optimality of rotor-router graph exploration

Authors: Artur Menc, Dominik Pająk, Przemysław Uznański

Abstract: We consider the problem of exploration of an anonymous, port-labeled, undirected graph with $n$ nodes and $m$ edges and diameter $D$, by a single mobile agent. Initially the agent does not know the graph topology nor any of the global parameters. Moreover, the agent does not know the incoming port when entering to a vertex. Each vertex is endowed with memory that can be read and modified by the ag… ▽ More We consider the problem of exploration of an anonymous, port-labeled, undirected graph with $n$ nodes and $m$ edges and diameter $D$, by a single mobile agent. Initially the agent does not know the graph topology nor any of the global parameters. Moreover, the agent does not know the incoming port when entering to a vertex. Each vertex is endowed with memory that can be read and modified by the agent upon its visit to that node. However the agent has no operational memory i.e., it cannot carry any state while traversing an edge. In such a model at least $\log_2 d$ bits are needed at each vertex of degree $d$ for the agent to be able to traverse each graph edge. This number of bits is always sufficient to explore any graph in time $O(mD)$ using algorithm Rotor-Router. We show that even if the available node memory is unlimited then time $Ω(n^3)$ is sometimes required for any algorithm. This shows that Rotor-Router is asymptotically optimal in the worst-case graphs. Secondly we show that for the case of the path the Rotor-Router attains exactly optimal time. △ Less

Submitted 29 November, 2015; v1 submitted 19 February, 2015; originally announced February 2015.

Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Authors: Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak

Abstract: The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $n\geq D\geq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $Ω(D\log (n/D))$ are identical. The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $n\geq D\geq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $Ω(D\log (n/D))$ are identical. △ Less

Submitted 9 March, 2015; v1 submitted 16 May, 2014; originally announced July 2014.