Search

Two firms are engaged in a competitive prediction task. Each firm has two sources of data -- labeled historical data and unlabeled inference-time data -- and uses the former to derive a prediction model, and the latter to make predictions on new instances. We study data-sharing contracts between the firms. The novelty of our study is to introduce and highlight the differences between contracts that share prediction models only, contracts to share inference-time predictions only, and contracts to share both. Our analysis proceeds on three levels. First, we develop a general Bayesian framework that facilitates our study. Second, we narrow our focus to two natural settings within this framework: (i) a setting in which the accuracy of each firm's prediction model is common knowledge, but the correlation between the respective models is unknown; and (ii) a setting in which two hypotheses exist regarding the optimal predictor, and one of the firms has a structural advantage in deducing it. Within these two settings we study optimal contract choice. More specifically, we find the individually rational and Pareto-optimal contracts for some notable cases, and describe specific settings where each of the different sharing contracts emerge as optimal. Finally, in the third level of our analysis we demonstrate the applicability of our concepts in a synthetic simulation using real loan data.

We consider the problem of dynamic channel allocation (DCA) in cognitive communication networks with the goal of maximizing a global signal-to-interference-plus-noise ratio (SINR) measure under a specified target quality of service (QoS)-SINR for each network. The shared bandwidth is partitioned into K channels with frequency separation. In contrast to the majority of existing studies that assume perfect orthogonality or a one- to-one user-channel allocation mapping, this paper focuses on real-world systems experiencing inter-carrier interference (ICI) and channel reuse by multiple large-scale networks. This realistic scenario significantly increases the problem dimension, rendering existing algorithms inefficient. We propose a novel multi-agent reinforcement learning (RL) framework for distributed DCA, named Channel Allocation RL To Overlapped Networks (CARLTON). The CARLTON framework is based on the Centralized Training with Decentralized Execution (CTDE) paradigm, utilizing the DeepMellow value-based RL algorithm. To ensure robust performance in the interference-laden environment we address, CARLTON employs a low-dimensional representation of observations, generating a QoS-type measure while maximizing a global SINR measure and ensuring the target QoS-SINR for each network. Our results demonstrate exceptional performance and robust generalization, showcasing superior efficiency compared to alternative state-of-the-art methods, while achieving a marginally diminished performance relative to a fully centralized approach.

Most text-to-3D generators build upon off-the-shelf text-to-image models trained on billions of images. They use variants of Score Distillation Sampling (SDS), which is slow, somewhat unstable, and prone to artifacts. A mitigation is to fine-tune the 2D generator to be multi-view aware, which can help distillation or can be combined with reconstruction networks to output 3D objects directly. In this paper, we further explore the design space of text-to-3D models. We significantly improve multi-view generation by considering video instead of image generators. Combined with a 3D reconstruction algorithm which, by using Gaussian splatting, can optimize a robust image-based loss, we directly produce high-quality 3D outputs from the generated views. Our new method, IM-3D, reduces the number of evaluations of the 2D generator network 10-100x, resulting in a much more efficient pipeline, better quality, fewer geometric inconsistencies, and higher yield of usable 3D assets.

Decentralized cryptocurrencies are payment systems that rely on aligning the incentives of users and miners to operate correctly and offer a high quality of service to users. Recent literature studies the mechanism design problem of the auction serving as a cryptocurrency's transaction fee mechanism (TFM). We find that a non-myopic modelling of miners falls close to another well-known problem: that of online buffer management for packet switching. The main difference is that unlike packets which are of a fixed size throughout their lifetime, in a financial environment, user preferences (and therefore revenue extraction) may be time-dependent. We study the competitive ratio guarantees given a certain discount rate, and show how existing methods from packet scheduling, which we call "the undiscounted case", perform suboptimally in the more general discounted setting. Most notably, we find a novel, simple, memoryless, and optimal deterministic algorithm for the semi-myopic case, when the discount factor is up to ~0.770018. We also present a randomized algorithm that achieves better performance than the best possible deterministic algorithm, for any discount rate., Comment: 30 pages, 5 figures

To allocate transactions to blocks, cryptocurrencies use an auction-like transaction fee mechanism (TFM). A conjecture of Roughgarden [44] asks whether there is a TFM that is incentive compatible for both the users and the miner, and is also resistant to off-chain agreements (OCAs) between these parties, a collusion notion that captures the ability of users and the miner to jointly deviate for profit. The work of Chung and Shi [12] tackles the problem using the different collusion resistance notion of side-channel proofness (SCP), and shows an impossibility given this notion. We show that OCA-proofness and SCP are different, with SCP being strictly stronger. We then fully characterize the intersection of deterministic dominant strategy incentive-compatible (DSIC) and OCA-proof mechanisms, as well as deterministic MMIC and OCA-proof ones, and use this characterization to show that only the trivial mechanism is DSIC, myopic miner incentive-compatible (MMIC) and OCA-proof. We also show that a randomized mechanism can be at most 0.842-efficient in the worst case, and that the impossibility of a non-trivial DSIC, MMIC and OCA-proof extends to a couple of natural classes of randomized mechanisms., Comment: 29 pages

In the fully-anonymous (shared-memory) model, inspired by a biological setting, processors have no identifiers and memory locations are anonymous. This means that there is no pre-existing agreement among processors on any naming of the memory locations. In this work, we ask fundamental questions about the fully-anonymous model in the hope to obtain a better understanding of the role of naming and anonymity in distributed computing. First, we ask what it means to solve a task under processor anonymity. With tasks such as renaming, the traditional notion obviously does not apply. Instead of restricting ourselves to colorless tasks, we propose using the notion of group solvability, which allows transferring any task to processor-anonymous models. Second, the difficulty with anonymity is that processors can hardly avoid covering and then overwriting each other's writes, erasing information written by their predecessors. To get to the bottom of this phenomenon, we ask what system configurations are stable when processors keep reading and writing ad infinitum. Resolving this question leads us to a wait-free solution to the snapshot task, which then allows us to solve renaming and obstruction-free consensus.

In a permissionless system like Ethereum, participation may fluctuate dynamically as some participants unpredictably go offline and some others come back online. In such an environment, traditional Byzantine fault-tolerant consensus algorithms may stall - even in the absence of failures - because they rely on the availability of fixed-sized quorums. The sleepy model formally captures the main requirements for solving consensus under dynamic participation, and several algorithms solve consensus with probabilistic safety in this model assuming that, at any time, more than half of the online participants are well behaved. However, whether safety can be ensured deterministically under these assumptions, especially with constant latency, remained an open question. Assuming a constant adversary, we answer in the positive by presenting a consensus algorithm that achieves deterministic safety and constant latency in expectation. In the full version of this paper, we also present a second algorithm which obtains both deterministic safety and liveness, but is likely only of theoretical interest because of its high round and message complexity. Both algorithms are striking in their simplicity.

Like Asynchrony, Mobility of faults precludes consensus. Yet, a model M in which Consensus is solvable, has an analogue relaxed model in which Consensus is not solvable and for which we can ask, whether Consensus is solvable if the system initially behaves like the relaxed analogue model, but eventually morphs into M. We consider two relaxed analogues of M. The first is the traditional Asynchronous model, and the second to be defined, the Mobile analogue. While for some M we show that Consensus is not solvable in the Asynchronous analogue, it is solvable in all the Mobile analogues. Hence, from this perspective Mobility is superior to Asynchrony. The pie in the sky relationship we envision is: Consensus is solvable in M, if and only if binary Commit-Adopt is solvable in the mobile analogue. The ``only if'' is easy. Here we show case by case that the ``if'' holds for all the common faults types.

We propose a new distributed-computing model, inspired by permissionless distributed systems such as Bitcoin and Ethereum, that allows studying permissionless consensus in a mathematically regular setting. Like in the sleepy model of Pass and Shi, we consider a synchronous, round-by-round message-passing system in which the set of online processors changes each round. Unlike the sleepy model, the set of processors may be infinite. Moreover, processors never fail; instead, an adversary can temporarily or permanently impersonate some processors. Finally, processors have access to a strong form of message-authentication that authenticates not only the sender of a message but also the round in which the message was sent. Assuming that, each round, the adversary impersonates less than 1/2 of the online processors, we present two consensus algorithms. The first ensures deterministic safety and constant latency in expectation, assuming a probabilistic leader-election oracle. The second ensures deterministic safety and deterministic liveness assuming irrevocable impersonation and eventually-stabilizing participation. The model is unrealistic in full generality. However, if we assume finitely many processes and that the set of faulty processes remains constant, the model coincides with a practically-motivated model: the static version of the sleepy model.

In the 1980s, three related impossibility results emerged in the field of distributed computing. First, Fischer, Lynch, and Paterson demonstrated that deterministic consensus is unattainable in an asynchronous message-passing system when a single process may crash-stop. Subsequently, Loui and Abu-Amara showed the infeasibility of achieving consensus in asynchronous shared-memory systems, given the possibility of one crash-stop failure. Lastly, Santoro and Widmayer established the impossibility of consensus in synchronous message-passing systems with a single process per round experiencing send-omission faults. In this paper, we revisit these seminal results. First, we observe that all these systems are equivalent in the sense of implementing each other. Then, we prove the impossibility of consensus in the synchronous system of Santoro and Widmayer, which is the easiest to reason about. Taking inspiration from V\"olzer's proof pearl and from the Borowski-Gafni simulation, we obtain a remarkably simple proof. We believe that a contemporary pedagogical approach to teaching these results should first address the equivalence of the systems before proving the consensus impossibility within the system where the result is most evident., Comment: Added reference to conference version, and corrected typos and small errors

Current diffusion or flow-based generative models for 3D shapes divide to two: distilling pre-trained 2D image diffusion models, and training directly on 3D shapes. When training a diffusion or flow models on 3D shapes a crucial design choice is the shape representation. An effective shape representation needs to adhere three design principles: it should allow an efficient conversion of large 3D datasets to the representation form; it should provide a good tradeoff of approximation power versus number of parameters; and it should have a simple tensorial form that is compatible with existing powerful neural architectures. While standard 3D shape representations such as volumetric grids and point clouds do not adhere to all these principles simultaneously, we advocate in this paper a new representation that does. We introduce Mosaic-SDF (M-SDF): a simple 3D shape representation that approximates the Signed Distance Function (SDF) of a given shape by using a set of local grids spread near the shape's boundary. The M-SDF representation is fast to compute for each shape individually making it readily parallelizable; it is parameter efficient as it only covers the space around the shape's boundary; and it has a simple matrix form, compatible with Transformer-based architectures. We demonstrate the efficacy of the M-SDF representation by using it to train a 3D generative flow model including class-conditioned generation with the 3D Warehouse dataset, and text-to-3D generation using a dataset of about 600k caption-shape pairs., Comment: More results and details can be found at https://lioryariv.github.io/msdf

We present Semantify: a self-supervised method that utilizes the semantic power of CLIP language-vision foundation model to simplify the control of 3D morphable models. Given a parametric model, training data is created by randomly sampling the model's parameters, creating various shapes and rendering them. The similarity between the output images and a set of word descriptors is calculated in CLIP's latent space. Our key idea is first to choose a small set of semantically meaningful and disentangled descriptors that characterize the 3DMM, and then learn a non-linear mapping from scores across this set to the parametric coefficients of the given 3DMM. The non-linear mapping is defined by training a neural network without a human-in-the-loop. We present results on numerous 3DMMs: body shape models, face shape and expression models, as well as animal shapes. We demonstrate how our method defines a simple slider interface for intuitive modeling, and show how the mapping can be used to instantly fit a 3D parametric body shape to in-the-wild images.

Background: It is important to understand patient preferences on managing low-risk papillary thyroid cancer (PTC). Methods: We prospectively followed patients with low-risk PTC <2 cm in maximal diameter, who were offered the choice of thyroidectomy or active surveillance (AS) at the University Health Network (UHN), in Toronto, Canada. The primary outcome was the frequency of AS choice (percentage with confidence interval [CI]). Univariate and multivariable analyses were performed to identify predictors of the choice of AS. Results: We enrolled 200 patients of median age 51 years (interquartile range 42-62). The primary tumor measured >1 cm in 55.5% (111/200) of participants. The AS was chosen by 77.5% [71.2-82.7%, 155/200] of participants. In a backwards conditional regression model, the clinical and demographic factors independently associated with choosing AS included: older age (compared with referent group <40 years)-age 40-64 years-odds ratio (OR) 2.78 [CI, 1.23-6.30, p = 0.014], age ≥65 years-OR 8.43 [2.13-33.37, p = 0.002], and education level of high school or lower-OR 4.41 [1.25-15.53, p = 0.021]; AS was inversely associated with the patient's surgeon of record being affiliated with the study hospital-OR 0.29 [0.11-0.76, p = 0.012]. In a separate backwards conditional logistic regression model examining associations with psychological characteristics, AS choice was independently associated with a fear of needing to take thyroid hormones after thyroidectomy-OR 1.24 [1.11-1.39, p < 0.001], but inversely associated with fear of PTC progression-OR 0.94 [0.90-0.98, p = 0.006] and an active coping mechanism ("doing something")-OR 0.43 [0.28-0.66, p < 0.001]. Conclusions: Approximately three-quarters of our participants chose AS over surgery. The factors associated with choosing AS included older age, lower education level, and having a surgeon outside the study institution. Patients' fears about either their PTC progressing or taking thyroid hormone replacement a

Social innovation refers to a novel way of addressing societal and environmental issues by leveraging the private sector’s expertise and ways of working to make a positive impact on the world’s “wicked”—complex, interconnected—problems. Business schools have historically had a tenuous relationship with social impact, especially in emerging economies, where the work of elite institutions has been both lauded and called into question. Power dynamics, cultural differences, and lack of familiarity with the local context have sometimes detracted from elite business school students’ well-intentioned aims—or created negative externalities and consequences. Based on a conceptual framework around pedagogy that incorporated business models, mindsets, and modes of instruction, interviews were conducted at six social impact centers in elite business schools. The findings suggest that such centers are moving away from a focus on business models toward a focus on mindsets. Instead of encouraging students to create standalone ventures, a practice known as social entrepreneurship, they are moving students toward an awareness of systems and what can drive change within them. Also, rather than emphasizing knowledge transfer by “parachuting in,” students are being taught to engage in a collaborative exchange with partners in emerging economies. This is the first study to look at the pedagogy of social impact at elite business schools with respect to emerging economies.

Recent text-to-image diffusion models are able to generate convincing results of unprecedented quality. However, it is nearly impossible to control the shapes of different regions/objects or their layout in a fine-grained fashion. Previous attempts to provide such controls were hindered by their reliance on a fixed set of labels. To this end, we present SpaText - a new method for text-to-image generation using open-vocabulary scene control. In addition to a global text prompt that describes the entire scene, the user provides a segmentation map where each region of interest is annotated by a free-form natural language description. Due to lack of large-scale datasets that have a detailed textual description for each region in the image, we choose to leverage the current large-scale text-to-image datasets and base our approach on a novel CLIP-based spatio-textual representation, and show its effectiveness on two state-of-the-art diffusion models: pixel-based and latent-based. In addition, we show how to extend the classifier-free guidance method in diffusion models to the multi-conditional case and present an alternative accelerated inference algorithm. Finally, we offer several automatic evaluation metrics and use them, in addition to FID scores and a user study, to evaluate our method and show that it achieves state-of-the-art results on image generation with free-form textual scene control., Comment: CVPR 2023. Project page available at: https://omriavrahami.com/spatext

Cryptocurrencies employ auction-esque transaction fee mechanisms (TFMs) to allocate transactions to blocks, and to determine how much fees miners can collect from transactions. Several impossibility results show that TFMs that satisfy a standard set of "good" properties obtain low revenue, and in certain cases, no revenue at all. In this work, we circumvent previous impossibilities by showing that when desired TFM properties are reasonably relaxed, simple mechanisms can obtain strictly positive revenue. By discretizing fees, we design a TFM that satisfies the extended TFM desiderata: it is dominant strategy incentive-compatible (DSIC), myopic miner incentive-compatible (MMIC), side-contract-proof (SCP) and obtains asymptotically optimal revenue (i.e., linear in the number of allocated bids), and optimal revenue when considering separable TFMs. If instead of discretizing fees we relax the DSIC and SCP properties, we show that Bitcoin's TFM, after applying the revelation principle, is Bayesian incentive-compatible (BIC), MMIC, off-chain-agreement (OCA) proof, and approximately revenue-optimal. We reach our results by characterizing the class of multi-item OCA-proof mechanisms, which may be of independent interest., Comment: 28 pages

We propose Make-A-Video -- an approach for directly translating the tremendous recent progress in Text-to-Image (T2I) generation to Text-to-Video (T2V). Our intuition is simple: learn what the world looks like and how it is described from paired text-image data, and learn how the world moves from unsupervised video footage. Make-A-Video has three advantages: (1) it accelerates training of the T2V model (it does not need to learn visual and multimodal representations from scratch), (2) it does not require paired text-video data, and (3) the generated videos inherit the vastness (diversity in aesthetic, fantastical depictions, etc.) of today's image generation models. We design a simple yet effective way to build on T2I models with novel and effective spatial-temporal modules. First, we decompose the full temporal U-Net and attention tensors and approximate them in space and time. Second, we design a spatial temporal pipeline to generate high resolution and frame rate videos with a video decoder, interpolation model and two super resolution models that can enable various applications besides T2V. In all aspects, spatial and temporal resolution, faithfulness to text, and quality, Make-A-Video sets the new state-of-the-art in text-to-video generation, as determined by both qualitative and quantitative measures.

Recent text-to-image models have achieved impressive results. However, since they require large-scale datasets of text-image pairs, it is impractical to train them on new domains where data is scarce or not labeled. In this work, we propose using large-scale retrieval methods, in particular, efficient k-Nearest-Neighbors (kNN), which offers novel capabilities: (1) training a substantially small and efficient text-to-image diffusion model without any text, (2) generating out-of-distribution images by simply swapping the retrieval database at inference time, and (3) performing text-driven local semantic manipulations while preserving object identity. To demonstrate the robustness of our method, we apply our kNN approach on two state-of-the-art diffusion backbones, and show results on several different datasets. As evaluated by human studies and automatic metrics, our method achieves state-of-the-art results compared to existing approaches that train text-to-image generation models using images only (without paired text data)

Recent text-to-image generation methods provide a simple yet exciting conversion capability between text and image domains. While these methods have incrementally improved the generated image fidelity and text relevancy, several pivotal gaps remain unanswered, limiting applicability and quality. We propose a novel text-to-image method that addresses these gaps by (i) enabling a simple control mechanism complementary to text in the form of a scene, (ii) introducing elements that substantially improve the tokenization process by employing domain-specific knowledge over key image regions (faces and salient objects), and (iii) adapting classifier-free guidance for the transformer use case. Our model achieves state-of-the-art FID and human evaluation results, unlocking the ability to generate high fidelity images in a resolution of 512x512 pixels, significantly improving visual quality. Through scene controllability, we introduce several new capabilities: (i) Scene editing, (ii) text editing with anchor scenes, (iii) overcoming out-of-distribution text prompts, and (iv) story illustration generation, as demonstrated in the story we wrote.

We consider an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics, where an unknown exogenous global Markov process governs the rewards distribution of each arm. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule, which is non-identical among different arms. At each time, a player chooses an arm out of N arms to play, and receives a random reward from a finite set of reward states. The arms are restless, that is, their local state evolves regardless of the player's actions. Motivated by recent studies on related RMAB settings, the regret is defined as the reward loss with respect to a player that knows the dynamics of the problem, and plays at each time t the arm that maximizes the expected immediate value. The objective is to develop an arm-selection policy that minimizes the regret. To that end, we develop the Learning under Exogenous Markov Process (LEMP) algorithm. We analyze LEMP theoretically and establish a finite-sample bound on the regret. We show that LEMP achieves a logarithmic regret order with time. We further analyze LEMP numerically and present simulation results that support the theoretical findings and demonstrate that LEMP significantly outperforms alternative algorithms., Comment: Accepted for presentation at IEEE ICASSP 2022. arXiv admin note: substantial text overlap with arXiv:2112.09484

Detection of anomalies among a large number of processes is a fundamental task that has been studied in multiple research areas, with diverse applications spanning from spectrum access to cyber-security. Anomalous events are characterized by deviations in data distributions, and thus can be inferred from noisy observations based on statistical methods. In some scenarios, one can often obtain noisy observations aggregated from a chosen subset of processes. Such hierarchical search can further minimize the sample complexity while retaining accuracy. An anomaly search strategy should thus be designed based on multiple requirements, such as maximizing the detection accuracy; efficiency, be efficient in terms of sample complexity; and be able to cope with statistical models that are known only up to some missing parameters (i.e., composite hypotheses). In this paper, we consider anomaly detection with observations taken from a chosen subset of processes that conforms to a predetermined tree structure with partially known statistical model. We propose Hierarchical Dynamic Search (HDS), a sequential search strategy that uses two variations of the Generalized Log Likelihood Ratio (GLLR) statistic, and can be used for detection of multiple anomalies. HDS is shown to be order-optimal in terms of the size of the search space, and asymptotically optimal in terms of detection accuracy. An explicit upper bound on the error probability is established for the finite sample regime. In addition to extensive experiments on synthetic datasets, experiments have been conducted on the DARPA intrusion detection dataset, showing that HDS is superior to existing methods., Comment: A short version of this paper was presented at IEEE International Symposium on Information Theory (ISIT) 2022

The quality of learning generally improves with the scale and diversity of data. Companies and institutions can therefore benefit from building models over shared data. Many cloud and blockchain platforms, as well as government initiatives, are interested in providing this type of service. These cooperative efforts face a challenge, which we call ``exclusivity attacks''. A firm can share distorted data, so that it learns the best model fit, but is also able to mislead others. We study protocols for long-term interactions and their vulnerability to these attacks, in particular for regression and clustering tasks. We conclude that the choice of protocol, as well as the number of Sybil identities an attacker may control, is material to vulnerability.

Stellar introduced a new type of quorum system called a Federated Byzantine Agreement System. A major difference between this novel type of quorum system and a threshold quorum system is that each participant has its own, personal notion of a quorum. Thus, unlike in a traditional BFT system, designed for a uniform notion of quorum, even in a time of synchrony one well-behaved participant may observe a quorum of well-behaved participants, while others may not. To tackle this new problem in a more general setting, we abstract the Stellar Network as an instance of what we call Personal Byzantine Quorum Systems. Using this notion, we streamline the theory behind the Stellar Network, removing the clutter of unnecessary details, and refute the conjecture that Stellar’s notion of intact set is optimally fault-tolerant. Most importantly, we develop a new consensus algorithm for the new setting.

The field of distributed computability studies whether a task is solvable in a distributed system, as specified by communication channels, failure patterns, synchronization instructions, etc. Tasks are analogs of functions in distributed computing, which characterizes the coordination problems in a system with multiple processes. Processes start with an input value in a task and then communicate with others to decide an output value. Unlike classical computability theory, task solvability depends on the model of the system. Determining whether a task is solvable in a given model is usually argued on a case-by-case basis.The celebrated asynchronous computability theorem (ACT) provides a topological characterization of task solvability in the wait-free model. Since the development of ACT, the topological method has achieved significant successes: ACT is generalized to models with additional synchronization objects and models of resiliency. The general theory of distributed computability, however, has still not been established. It is not clear whether ACT can be generalized for more general models.In this dissertation, we study task computability in more general models. We show that every set-consensus collection model is equivalent to a vector-set-consensus model. For colorless task solvability, we derive ACT of the vector-set-consensus model. For colored tasks in the k-set-consensus model, we present an alternative formulation of ACT by introducing the notion of color-projection closed complex. For models specified by resiliency, we study the general adversary model and derive the “wait-atbeginning” ACT for colorless tasks. More specifically, we show that processes only need the full power of the adversary at the beginning of a colorless task protocol. We also present a sufficient topological condition to ensure that a task has a solution in the vector-set-consensus model. Specifically, we show that if the task output complex satisfies certain topological properties, it can

BACKGROUND: The traditional management of papillary thyroid cancer (PTC) is thyroidectomy (total or partial removal of the thyroid). Active surveillance (AS) may be considered as an alternative option for small, low risk PTC. AS involves close follow-up (including regularly scheduled clinical and radiological assessments), with the intention of intervening with surgery for disease progression or patient preference. METHODS: This is a protocol for a prospective, observational, long-term follow-up multi-centre Canadian cohort study. Consenting eligible adults with small, low risk PTC (< 2cm in maximal diameter, confined to the thyroid, and not immediately adjacent to critical structures in the neck) are offered the choice of AS or surgery for management of PTC. Patient participants are free to choose either option (AS or surgery) and the disease management course is thus not assigned by the investigators. Surgery is provided as usual care by a surgeon in an institution of the patient's choice. Our primary objective is to determine the rate of 'failure' of disease management in respective AS and surgical arms as defined by: i) AS arm - surgery for progression of PTC, and ii) surgical arm - surgery or other treatment for disease persistence or progression after completing initial treatment. Secondary outcomes include long-term thyroid oncologic and treatment outcomes, as well as patient-reported outcomes. DISCUSSION: The results from this study will provide long-term clinical and patient reported outcome evidence regarding active surveillance or immediate surgery for management of small, low risk PTC. This will inform future clinical trials in disease management of small, low risk papillary thyroid cancer. REGISTRATION DETAILS: This prospective observational cohort study is registered on clinicaltrials.gov (NCT04624477), but it should not be considered a clinical trial as there is no assigned intervention and patients are free to choose either AS or surgery.

Colorectal cancer risk stratification is crucial to improve screening and risk-reducing recommendations, and consequently do better than a one-size-fits-all screening regimen. Current screening guidelines in the UK, USA and Australia focus solely on family history and age for risk prediction, even though the vast majority of the population do not have any family history. We investigated adding a polygenic risk score based on 45 single-nucleotide polymorphisms to a family history model (combined model) to quantify how it improves the stratification and discriminatory performance of 10-year risk and full lifetime risk using a prospective population-based cohort within the UK Biobank. For both 10-year and full lifetime risk, the combined model had a wider risk distribution compared with family history alone, resulting in improved risk stratification of nearly 2-fold between the top and bottom risk quintiles of the full lifetime risk model. Importantly, the combined model can identify people (n = 72,019) who do not have family history of colorectal cancer but have a predicted risk that is equivalent to having at least one affected first-degree relative (n = 44,950). We also confirmed previous findings by showing that the combined full lifetime risk model significantly improves discriminatory accuracy compared with a simple family history model 0.673 (95% CI 0.664-0.682) versus 0.666 (95% CI 0.657-0.675), p = 0.0065. Therefore, a combined polygenic risk score and first-degree family history model could be used to improve risk stratified population screening programs.

We describe our experience conducting a prospective observational cohort study on the management of small, low risk papillary thyroid cancer during the COVID-19 pandemic. Our study participants are given the choice of active surveillance (AS) or surgery, and those in the AS arm are followed at the study center, whereas surgical patients undergo usual care. During the pandemic we have transitioned from in-person research patient visits to largely virtual care of patients under AS. As of 30 October 2020, we had enrolled 181 patients enrolled in our study (including 25 during the pandemic), of which 92.3% (167/181) consented to telephone communication and 79.0% (143/181) consented to secure videoconferencing communication. Prior to the pandemic, 74.5% (117/157) of our patients chose AS over surgery, whereas during the pandemic, 96.0% (24/25) chose AS. Of the 133 study patients who were under AS within the timeframe from 12 March 2020, to 30 October 2020, the percentage of patients who missed appointments was 8.3% (11/133, for neck ultrasound and physician visits, respectively) and delayed appointments was 23.3% (31/133). This preliminary data suggests that prospective observational research on AS of thyroid cancer can safely continue during the pandemic.

Active surveillance (AS) in the management of small, low risk papillary thyroid cancer (PTC) as an alternative option to thyroidectomy, is an area of active research. A national Canadian study is proposed to evaluate the long-term outcomes of patients with small, low risk PTC who choose AS or surgery. This letter describes the proceedings of a national investigator meeting to plan the study.

This study focuses on the launch phase of the leading reward-based crowdfunding market—Kickstarter. It documents the behavior of male and female entrepreneurs in raising early stage capital. We find that women share as entrepreneurs in the platform (34.7%) does not equal to their share in the overall population, and they are concentrated in stereotyped sectors, both as entrepreneurs and as backers. We also find that women do not set lower funding goals than men, they enjoy higher rates of success than men, even after controlling for project categories and funding goals, and that backers of both genders have a tendency to fund entrepreneurs of their own gender. Our survey of Kickstarter backers finds evidence of taste-based discrimination by male backers., QC 20210609

We consider an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics, where an unknown exogenous global Markov process governs the rewards distribution of each arm. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule, which is non-identical among different arms. At each time, a player chooses an arm out of $N$ arms to play, and receives a random reward from a finite set of reward states. The arms are restless, that is, their local state evolves regardless of the player's actions. Motivated by recent studies on related RMAB settings, the regret is defined as the reward loss with respect to a player that knows the dynamics of the problem, and plays at each time $t$ the arm that maximizes the expected immediate value. The objective is to develop an arm-selection policy that minimizes the regret. To that end, we develop the Learning under Exogenous Markov Process (LEMP) algorithm. We analyze LEMP theoretically and establish a finite-sample bound on the regret. We show that LEMP achieves a logarithmic regret order with time. We further analyze LEMP numerically and present simulation results that support the theoretical findings and demonstrate that LEMP significantly outperforms alternative algorithms., Comment: 13 pages, 6 figures. arXiv admin note: text overlap with arXiv:1906.08120

For finite integer squares, we consider the problem of learning a classification $I$ that respects Pareto domination. The setup is natural in dynamic programming settings. We show that a generalization of the binary search algorithm achieves an optimal $\theta(n)$ worst-case run time., Comment: Found that this is a restatement of a known algorithm called Saddleback search: https://link.springer.com/chapter/10.1007/11783596_8

We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1)~the existence of EFX and other solution concepts for goods with copies; (2)~the existence of EFX and other solution concepts for chores. We establish a tight relation between these issues via two conceptual contributions: First, a refinement of envy-based fairness notions that we term envy \emph{without commons} (denoted $\efxwc$ when applied to EFX). Second, a formal \emph{duality theorem} relating the existence of a host of (refined) fair allocation concepts for copies to their existence for chores. We demonstrate the usefulness of our duality result by using it to characterize the existence of EFX for chores through the dual environment, as well as to prove EFX existence in the special case of leveled preferences over the chores. We further study the hierarchy among envy-freeness notions without commons and their $\alpha$-MMS guarantees, showing for example that any $\efxwc$ allocation guarantees at least $\frac{4}{11}$-MMS for goods with copies.

Weighted voting games apply to a wide variety of multi-agent settings. They enable the formalization of power indices which quantify the coalitional power of players. We take a novel approach to the study of the power of big vs.~small players in these games. We model small (big) players as having single (multiple) votes. The aggregate relative power of big players is measured w.r.t.~their votes proportion. For this ratio, we show small constant worst-case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp contrast, this ratio is unbounded for the Banzhaf index. As an application, we define a false-name strategic normal form game where each big player may split its votes between false identities, and study its various properties. Together, our results provide foundations for the implications of players' size, modeled as their ability to split, on their relative power.

We study competition among contests in a general model that allows for an arbitrary and heterogeneous space of contest design, where the goal of the contest designers is to maximize the contestants' sum of efforts. Our main result shows that optimal contests in the monopolistic setting (i.e., those that maximize the sum of efforts in a model with a single contest) form an equilibrium in the model with competition among contests. Under a very natural assumption these contests are in fact dominant, and the equilibria that they form are unique. Moreover, equilibria with the optimal contests are Pareto-optimal even in cases where other equilibria emerge. In many natural cases, they also maximize the social welfare.

The dramatic success of deep learning is largely due to the availability of data. Data samples are often acquired on edge devices, such as smart phones, vehicles and sensors, and in some cases cannot be shared due to privacy considerations. Federated learning is an emerging machine learning paradigm for training models across multiple edge devices holding local datasets, without explicitly exchanging the data. Learning in a federated manner differs from conventional centralized machine learning, and poses several core unique challenges and requirements, which are closely related to classical problems studied in the areas of signal processing and communications. Consequently, dedicated schemes derived from these areas are expected to play an important role in the success of federated learning and the transition of deep learning from the domain of centralized servers to mobile edge devices. In this article, we provide a unified systematic framework for federated learning in a manner that encapsulates and highlights the main challenges that are natural to treat using signal processing tools. We present a formulation for the federated learning paradigm from a signal processing perspective, and survey a set of candidate approaches for tackling its unique challenges. We further provide guidelines for the design and adaptation of signal processing and communication methods to facilitate federated learning at large scale., Comment: 24 pages, 15 figures

The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open. We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions.

Background: Active surveillance (AS) of small, low-risk papillary thyroid cancers (PTCs) is increasingly being considered. There is limited understanding of why individuals with low-risk PTC may choose AS over traditional surgical management. Methods: We present a mixed-methods analysis of a prospective observational real-life decision-making study regarding the choice of thyroidectomy or AS for management of localized, low-risk PTCs <2 cm in maximum diameter (NCT03271892). Patients were provided standardized medical information and were interviewed after making their decision (which dictated disease management). We evaluated patients' levels of decision-self efficacy (confidence in medical decision-making ability) at the time information was presented and their level of decision satisfaction after finalizing their decision (using standardized questionnaires). We asked patients to explain the reason for their choice and qualitatively analyzed the results. Results: We enrolled 74 women and 26 men of mean age 52.4 years, with a mean PTC size of 11.0 mm (interquartile range 9.0, 14.0 mm). Seventy-one patients (71.0% [95% confidence interval 60.9-79.4%]) chose AS over surgery. Ninety-four percent (94/100) of participants independently made their own disease management choice; the rest shared the decision with their physician. Participants had a high baseline level of decision self-efficacy (mean 94.3, standard deviation 9.6 on a 100-point scale). Almost all (98%, 98/100) participants reported high decision satisfaction. Factors reported by patients as influencing their decision included the following: perceived risk of thyroidectomy or the cancer, family considerations, treatment timing in the context of life circumstances, and trust in health care providers. Conclusions: In this Canadian study, ∼7 out of 10 patients with small, low-risk PTC, who were offered the choice of AS or surgery, chose AS. Personal perceptions about cancer or thyroidectomy, contextual factors, f

Crowdfunding has created new opportunities for poor microentrepreneurs. One crucial question is the impact that the purpose of a loan—either business investment or basic necessities—may have on the success of a campaign. Investigating aprosocial crowdfunding platform, we fnd that loans taken out to meet basic needs are funded faster than business-relatedloans, especially for small amounts, which can be explained by the prosocial motivation of microlenders. Moreover, femalemicroborrowers are funded faster than men, especially for basic needs loans. Our results therefore suggest an ethical blindspot, since prosocially motivated crowdlenders may unintentionally end up producing adverse efects, replicating genderrole by supporting women to a lesser extent when they apply for business loans. This fnding expands prosocial motivationaltheory in ethical fnance., QC 20211206

We present a novel method for inserting objects, specifically humans, into existing images, such that they blend in a photorealistic manner, while respecting the semantic context of the scene. Our method involves three subnetworks: the first generates the semantic map of the new person, given the pose of the other persons in the scene and an optional bounding box specification. The second network renders the pixels of the novel person and its blending mask, based on specifications in the form of multiple appearance components. A third network refines the generated face in order to match those of the target person. Our experiments present convincing high-resolution outputs in this novel and challenging application domain. In addition, the three networks are evaluated individually, demonstrating for example, state of the art results in pose transfer benchmarks.

We present dynamic neural radiance fields for modeling the appearance and dynamics of a human face. Digitally modeling and reconstructing a talking human is a key building-block for a variety of applications. Especially, for telepresence applications in AR or VR, a faithful reproduction of the appearance including novel viewpoints or head-poses is required. In contrast to state-of-the-art approaches that model the geometry and material properties explicitly, or are purely image-based, we introduce an implicit representation of the head based on scene representation networks. To handle the dynamics of the face, we combine our scene representation network with a low-dimensional morphable model which provides explicit control over pose and expressions. We use volumetric rendering to generate images from this hybrid representation and demonstrate that such a dynamic neural scene representation can be learned from monocular input data only, without the need of a specialized capture setup. In our experiments, we show that this learned volumetric representation allows for photo-realistic image generation that surpasses the quality of state-of-the-art video-based reenactment methods., Comment: Video: https://youtu.be/m7oROLdQnjk | Project page: https://gafniguy.github.io/4D-Facial-Avatars

The task of motion transfer between a source dancer and a target person is a special case of the pose transfer problem, in which the target person changes their pose in accordance with the motions of the dancer. In this work, we propose a novel method that can reanimate a single image by arbitrary video sequences, unseen during training. The method combines three networks: (i) a segmentation-mapping network, (ii) a realistic frame-rendering network, and (iii) a face refinement network. By separating this task into three stages, we are able to attain a novel sequence of realistic frames, capturing natural motion and appearance. Our method obtains significantly better visual quality than previous methods and is able to animate diverse body types and appearances, which are captured in challenging poses, as shown in the experiments and supplementary video.

To unlock video chat for hundreds of millions of people hindered by poor connectivity or unaffordable data costs, we propose to authentically reconstruct faces on the receiver's device using facial landmarks extracted at the sender's side and transmitted over the network. In this context, we discuss and evaluate the benefits and disadvantages of several deep adversarial approaches. In particular, we explore quality and bandwidth trade-offs for approaches based on static landmarks, dynamic landmarks or segmentation maps. We design a mobile-compatible architecture based on the first order animation model of Siarohin et al. In addition, we leverage SPADE blocks to refine results in important areas such as the eyes and lips. We compress the networks down to about 3MB, allowing models to run in real time on iPhone 8 (CPU). This approach enables video calling at a few kbits per second, an order of magnitude lower than currently available alternatives., Comment: 11 pages

The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.

Stellar introduced a new type of quorum system called a Federated Byzantine Agreement System. A major difference between this novel type of quorum system and a threshold quorum system is that each participant has its own, personal notion of a quorum. Thus, unlike in a traditional BFT system, designed for a uniform notion of quorum, even in a time of synchrony one well-behaved participant may observe a quorum of well-behaved participants, while others may not. To tackle this new problem in a more general setting, we abstract the Stellar Network as an instance of what we call Personal Byzantine Quorum Systems. Using this notion, we streamline the theory behind the Stellar Network, removing the clutter of unnecessary details, and refute the conjecture that Stellar's notion of intact set is optimally fault-tolerant. Most importantly, we develop a new consensus algorithm for the new setting.

We propose a method for face de-identification that enables fully automatic video modification at high frame rates. The goal is to maximally decorrelate the identity, while having the perception (pose, illumination and expression) fixed. We achieve this by a novel feed-forward encoder-decoder network architecture that is conditioned on the high-level representation of a person's facial image. The network is global, in the sense that it does not need to be retrained for a given video or for a given identity, and it creates natural looking image sequences with little distortion in time., Comment: ICCV 2019

VCG is a classical combinatorial auction that maximizes social welfare. However, while the standard single-item Vickrey auction is false-name-proof, a major failure of multi-item VCG is its vulnerability to false-name attacks. This occurs already in the natural bare minimum model in which there are two identical items and bidders are single-minded. Previous solutions to this challenge focused on developing alternative mechanisms that compromise social welfare. We re-visit the VCG auction vulnerability and consider the bidder behavior in Bayesian settings. In service of that we introduce a novel notion, termed the granularity threshold, that characterizes VCG Bayesian resilience to false-name attacks as a function of the bidder type distribution. Using this notion we show a large class of cases in which VCG indeed obtains Bayesian resilience for the two-item single-minded setting., Comment: A partial and preliminary version of this paper has appeared in The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20). Supporting code for generating the article's figures can be found at https://github.com/yotam-gafni/vcg_bayesian_fnp