BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

JiaLin Zhang

JiaLin Zhang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and Algorithmsquant-phMachine LearningSocial and Information NetworksComputer Science and Game Theorygr-qcComputational Complexityhep-thArtificial IntelligenceComputer Visioncond-mat.mtrl-sciCryptography and SecurityDiscrete MathematicsDistributed, Parallel, and Cluster Computingeess.IVInformation Theorymath.ITmath.STnucl-thphysics.opticsphysics.soc-phStatistics Theory

Catalog footprint

What is connected

31works
22topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

31 published item(s)

preprint2026arXiv

On the Fair Allocation to Asymmetric Agents with Binary XOS Valuations

We study the problem of allocating $m$ indivisible goods among $n$ agents, where each agent's valuation is fractionally subadditive (XOS). With respect to AnyPrice Share (APS) fairness, Kulkarni et al. (2024) showed that, when agents have binary marginal values, a $0.1222$-APS allocation can be found in polynomial time, and there exists an instance where no allocation is better than $0.5$-approximate APS. Very recently, Feige and Grinberg (2025) extended the problem to the asymmetric case, where agents may have different entitlements, and improved the approximation ratio to $1/6$ for general XOS valuations. In this work, we focus on the asymmetric setting with binary XOS valuations, and further improve the approximation ratio to $1/2$, which matches the known upper bound. We also present a polynomial-time algorithm to compute such an allocation. Beyond APS fairness, we also study the weighted maximin share (WMMS) fairness. Farhadi et al. (2019) showed that, a $1/n$-WMMS allocation always exists for agents with general additive valuations, and that this approximation ratio is tight. We extend this result to general XOS valuations, where a $1/n$-WMMS allocation still exists, and this approximation ratio cannot be improved even when marginal values are binary. This shows a sharp contrast to binary additive valuations, where an exact WMMS allocation exists and can be found in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

SRFlow: A Dataset and Regularization Model for High-Resolution Facial Optical Flow via Splatting Rasterization

Facial optical flow supports a wide range of tasks in facial motion analysis. However, the lack of high-resolution facial optical flow datasets has hindered progress in this area. In this paper, we introduce Splatting Rasterization Flow (SRFlow), a high-resolution facial optical flow dataset, and Splatting Rasterization Guided FlowNet (SRFlowNet), a facial optical flow model with tailored regularization losses. These losses constrain flow predictions using masks and gradients computed via difference or Sobel operator. This effectively suppresses high-frequency noise and large-scale errors in texture-less or repetitive-pattern regions, enabling SRFlowNet to be the first model explicitly capable of capturing high-resolution skin motion guided by Gaussian splatting rasterization. Experiments show that training with the SRFlow dataset improves facial optical flow estimation across various optical flow models, reducing end-point error (EPE) by up to 42% (from 0.5081 to 0.2953). Furthermore, when coupled with the SRFlow dataset, SRFlowNet achieves up to a 48% improvement in F1-score (from 0.4733 to 0.6947) on a composite of three micro-expression datasets. These results demonstrate the value of advancing both facial optical flow estimation and micro-expression recognition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Asymptotic Normality for Plug-in Estimators of Generalized Shannon's Entropy

Shannon's entropy is one of the building blocks of information theory and an essential aspect of Machine Learning methods (e.g., Random Forests). Yet, it is only finitely defined for distributions with fast decaying tails on a countable alphabet. The unboundedness of Shannon's entropy over the general class of all distributions on an alphabet prevents its potential utility from being fully realized. To fill the void in the foundation of information theory, Zhang (2020) proposed generalized Shannon's entropy, which is finitely defined everywhere. The plug-in estimator, adopted in almost all entropy-based ML method packages, is one of the most popular approaches to estimating Shannon's entropy. The asymptotic distribution for Shannon's entropy's plug-in estimator was well studied in the existing literature. This paper studies the asymptotic properties for the plug-in estimator of generalized Shannon's entropy on countable alphabets. The developed asymptotic properties require no assumptions on the original distribution. The proposed asymptotic properties allow interval estimation and statistical tests with generalized Shannon's entropy.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into $d$ components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest $d$ rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder non-oblivious setting. We show non-oblivious setting incurs $Ω(T)$ pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys $o(T)$ policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for $K$-armed bandit and bandit convex optimization, we have $\mathcal{O}(T^{2/3})$ policy regret bound. We also prove a matching lower bound for $K$-armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is non-oblivious. It answers the open problem proposed in \cite{wang2021adaptive}, showing that non-oblivious delay is enough to incur $\tildeΩ(T^{2/3})$ regret.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Does acceleration assist entanglement harvesting?

We explore whether acceleration assists entanglement harvesting for a pair of uniformly accelerated detectors in three different acceleration scenarios, i.e., parallel, anti-parallel and mutually perpendicular acceleration, both in the sense of the entanglement harvested and harvesting-achievable separation between the two detectors. Within the framework of entanglement harvesting protocols and the Unruh-DeWitt model of detectors locally interacting with massless scalar fields via a Gaussian switching function with an interaction duration parameter, we find that, in the sense of the entanglement harvested, acceleration is a mixed blessing insofar as it increases the harvested entanglement for a large detector energy gap relative to the interaction duration parameter, whilst inhibiting the entanglement harvested for a small energy gap. Regarding the harvesting-achievable separation range between the detectors, we further find that for very small acceleration and large energy gap, both relative to the duration parameter, acceleration-assisted enhancement can happen in all three acceleration scenarios. This is in sharp contrast to what was argued previously: that the harvesting-achievable range can be enhanced only for anti-parallel acceleration. However, for a not too small acceleration relative to the duration parameter and an energy gap larger than the acceleration, we find that only detectors in parallel acceleration possess a harvesting-achievable range larger than those at rest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient quantum circuit synthesis for SAT-oracle with limited ancillary qubit

How to implement quantum oracle with limited resources raises concerns these days. We design two ancilla-adjustable and efficient algorithms to synthesize SAT-oracle, the key component in solving SAT problems. The previous work takes 2m-1 ancillary qubits and O(m) elementary gates to synthesize an m clauses oracle. The first algorithm reduces the number of ancillary qubits to 2\sqrt{m}, with at most an eightfold increase in circuit size. The number of ancillary qubits can be further reduced to 3 with a quadratic increase in circuit size. The second algorithm aims to reduce the circuit depth. By leveraging of the second algorithm, the circuit depth can be reduced to O(log m) with m ancillary qubits.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Harvesting Entanglement by non-identical detectors with different energy gaps

It has been shown that the vacuum state of a free quantum field is entangled and such vacuum entanglement can be harvested by a pair of initially uncorrelated detectors interacting locally with the vacuum field for a finite time. In this paper, we examine the entanglement harvesting phenomenon of two non-identical inertial detectors with different energy gaps locally interacting with massless scalar fields via a Gaussian switching function. We focus on how entanglement harvesting depends on the energy gap difference from two perspectives: the amount of entanglement harvested and the harvesting-achievable separation between the two detectors. In the sense of the amount of entanglement, we find that as long as the inter-detector separation is not too small with respect to the interaction duration parameter, two non-identical detectors could extract more entanglement from the vacuum state than the identical detectors. There exists an optimal value of the energy gap difference when the inter-detector separation is sufficiently large that renders the harvested entanglement to peak. Regarding the harvesting-achievable separation, we further find that the presence of an energy gap difference generally enlarges the harvesting-achievable separation range. Our results suggest that the non-identical detectors may be advantageous to extracting entanglement from vacuum in certain circumstances as compared to identical detectors.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Higher order monotonicity and submodularity of influence in social networks: from local to global

Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function $σ(S)$ is monotone and submodular, where $S$ is a seed set and the spread function $σ(S)$ denotes the expected number of active nodes at termination of a diffusion process starting from $S$. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD-k (Alternating Difference-$k$) as a generalization of monotonicity and submodularity. Specifically, a set function $f$ is called \adk if all the $\ell$-th order differences of $f$ on all inputs have sign $(-1)^{\ell+1}$ for every $\ell\leq k$. Note that AD-1 corresponds to monotonicity and AD-2 corresponds to monotonicity and submodularity. We propose a refined version of KKT's conjecture: in the general threshold model, local AD-k implies global AD-k. The original KKT conjecture corresponds to the case for AD-2, and the case for AD-1 is the trivial one of local monotonicity implying global monotonicity. By utilizing continuous extensions of set functions as well as social graph constructions, we prove the correctness of our conjecture when the social graph is a directed acyclic graph (DAG). Furthermore, we affirm our conjecture on general social graphs when $k=\infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Network Inference and Influence Maximization from Samples

Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the influence spread from these seeds. It has been widely investigated in the past two decades. In the canonical setting, the social network and its diffusion parameters are given as input. In this paper, we consider the more realistic sampling setting where the network is unknown and we only have a set of passively observed cascades that record the sets of activated nodes at each diffusion step. We study the task of influence maximization from these cascade samples (IMS) and present constant approximation algorithms for it under mild conditions on the seed set distribution. To achieve the optimization goal, we also provide a novel solution to the network inference problem, that is, learning diffusion parameters and the network structure from the cascade data. Compared with prior solutions, our network inference algorithms require weaker assumptions and do not rely on maximum-likelihood estimation and convex programming. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn, and we do not need any assumption related to the network structure or diffusion parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback

We study the online influence maximization (OIM) problem in social networks, where the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade in multiple rounds. In the demand of the real world, we work with node-level feedback instead of the common edge-level feedback in the literature. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Previously, there is a nearly optimal $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the linear threshold (LT) diffusion model with node-level feedback. It remains unknown whether the same algorithm exists for the independent cascade (IC) diffusion model. In this paper, we resolve this open problem by presenting an $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the IC model with node-level feedback.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Online Scheduling of Time-Critical Tasks to Minimize the Number of Calibrations

We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take $λ$ time steps as the activation time, and then the machine will remain calibrated status for $T$ time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an $\mathcal{O}(λ)$-competitive algorithm, which is asymptotically optimal. When $λ=0$, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of $3e+7(\approx 15.16)$ which improves upon the previous results for such problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Algorithm for Online Convex Optimization

We explore whether quantum advantages can be found for the zeroth-order online convex optimization problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a $T$ round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of online convex optimization. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles $O(1)$ times in each round as feedback, we give a quantum algorithm that achieves $O(\sqrt{T})$ regret without additional dependence of the dimension $n$, which outperforms the already known optimal classical algorithm only achieving $O(\sqrt{nT})$ regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve $O(\log T)$ regret with $O(1)$ queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $Ω(\sqrt{T})$ regret. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with $O(\mbox{poly}(\log T))$ regrets, exponentially improving the dependence in terms of $T$. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Discouraging Pool Block Withholding Attacks in Bitcoins

The arisen of Bitcoin has led to much enthusiasm for blockchain research and block mining, and the extensive existence of mining pools helps its participants (i.e., miners) gain reward more frequently. Recently, the mining pools are proved to be vulnerable for several possible attacks, and pool block withholding attack is one of them: one strategic pool manager sends some of her miners to other pools and these miners pretend to work on the puzzles but actually do nothing. And these miners still get reward since the pool manager can not recognize these malicious miners. In this work, we revisit the game-theoretic model for pool block withholding attacks and propose a revised approach to reallocate the reward to the miners. Fortunately, in the new model, the pool managers have strong incentive to not launch such attacks. We show that for any number of mining pools, no-pool-attacks is always a Nash equilibrium. Moreover, with only two minority mining pools participating, no-pool-attacks is actually the unique Nash equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a universal solution to the transport-of-intensity equation

Transport-of-intensity equation (TIE) is one of the most well-known approaches for phase retrieval and quantitative phase imaging. It directly recovers the quantitative phase distribution of an optical field by through-focus intensity measurements in a noninterferometic, deterministic manner. Nevertheless, the accuracy and validity of state-of-the-art TIE solvers depend on restrictive preknowledge or assumptions, including appropriate boundary conditions, a well-defined closed region, and quasi-uniform in-focus intensity distribution, which, however, cannot be strictly satisfied simultaneously under practical experimental conditions. In this Letter, we propose a universal solution to TIE with the advantages of high accuracy, convergence guarantee, applicability to arbitrarily-shaped regions, and simplified implementation and computation. With the "maximum intensity assumption", we firstly simplified TIE as a standard Possion equation to get an initial guess of the solution. Then the initial solution is further refined iteratively by solving the same Possion equation, and thus, the instability associated with the division by zero/small intensity values and large intensity variations can be effectively bypassed. Simulations and experiments with arbitrary phase, arbitrary aperture shapes, and nonuniform intensity distributions verify the effectiveness and universality of the proposed method.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimization from Structured Samples for Coverage Functions

We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we cannot obtain a constant approximation ratio for the maximum coverage problem using polynomially many independent samples of the form $\{S_i, f(S_i)\}_{i=1}^t$ (Balkanski et al., 2017), even if coverage functions are $(1 - ε)$-PMAC learnable using these samples (Badanidiyuru et al., 2012), which means most of the function values can be approximately learned very well with high probability. In this work, to circumvent the impossibility result of OPS, we propose a stronger model called optimization from structured samples (OPSS) for coverage functions, where the data samples encode the structural information of the functions. We show that under three general assumptions on the sample distributions, we can design efficient OPSS algorithms that achieve a constant approximation for the maximum coverage problem. We further prove a constant lower bound under these assumptions, which is tight when not considering computational efficiency. Moreover, we also show that if we remove any one of the three assumptions, OPSS for the maximum coverage problem has no constant approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Search with Prior Knowledge

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

The BTZ black hole exhibits anti-Hawking phenomena

The Unruh effect is a surprising prediction of quantum field theory that asserts accelerating observers perceive a thermal spectrum of particles with a temperature proportional to their acceleration. However, it has recently been shown that particle detectors can click less often or even cool down as their acceleration increases, in contrast to the heating one would expect. This leads to the so called anti-Unruh phenomena. Here we consider detectors outside a BTZ black hole and demonstrate the existence of black hole analogues of these effects, which we dub anti-Hawking phenomena.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Communities in Preference Networks: Refined Axioms and Beyond

Borgs et al. [2016] investigated essential requirements for communities in preference networks. They defined six axioms on community functions, i.e., community detection rules. Though having elegant properties, the practicality of this axiom system is compromised by the intractability of checking two critical axioms, so no nontrivial consistent community function was reported inBorgs et al. [2016] By adapting the two axioms in a natural way, we propose two new axioms that are efficiently-checkable. We show that most of the desirable properties of the original axiom system are preserved. More importantly, the new axioms provide a general approach to constructing consistent community functions. We further find a natural consistent community function that is also enumerable and samplable, answering an open problem in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising

In this work, we study the guaranteed delivery model which is widely used in online display advertising. In the guaranteed delivery scenario, ad exposures (which are also called impressions in some works) to users are guaranteed by contracts signed in advance between advertisers and publishers. A crucial problem for the advertising platform is how to fully utilize the valuable user traffic to generate as much as possible revenue. Different from previous works which usually minimize the penalty of unsatisfied contracts and some other cost (e.g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user traffic consumed to satisfy all contracts. Under this model, we develop a near optimal method to deliver ads for users. The main advantage of our method lies in that it consumes nearly as least as possible user traffic to satisfy all contracts, therefore more contracts can be accepted to produce more revenue. It also enables the publishers to estimate how much user traffic is redundant or short so that they can sell or buy this part of traffic in bulk in the exchange market. Furthermore, it is robust with regard to priori knowledge of user type distribution. Finally, the simulation shows that our method outperforms the traditional state-of-the-art methods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Optimality of Tape Merge of Two Lists with Similar Size

The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp \cite{taocp} independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In the seminal papers, Stockmeyer and Yao\cite{yao}, Murphy and Paull\cite{3k3}, and Christen\cite{christen1978optimality} independently showed when the lists to be merged are of size $m$ and $n$ satisfying $m\leq n\leq\lfloor\frac{3}{2}m\rfloor+1$, the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we used to prove lower bounds is Knuth's adversary methods \cite{taocp}. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. We also develop a new inequality about Knuth's adversary methods, which might be interesting in its own right. Moreover, we design a simple procedure to achieve constant improvement of the upper bounds for $2m-2\leq n\leq 3m $.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strongly Modulated Ambipolar Characteristics of Few-layer Black Phosphorus in Oxygen

Two-dimensional black phosphorus has been configured as field-effect transistors, showing an intrinsic symmetric ambipolar transport characteristic. Here, we demonstrate the strongly modulated ambipolar characteristics of few-layer black phosphorus in oxygen. Pure oxygen exposure can dramatically decrease the electron mobility of black phosphorus without degrading the hole transport. The transport characteristics can be nearly recovered upon annealing in Argon. This reveals that oxygen molecules are physisorbed on black phosphorus. In contrast, oxygen exposure upon light illumination exhibits a significant attenuation for both electron and hole transport, originating from the photoactivated oxidation of black phosphorus, which is corroborated by in situ X-ray photoelectron spectroscopy characterization. Our findings clarify the predominant role of oxygen in modulating ambipolar characteristics of black phosphorus, thereby providing deeper insight to the design of black phosphorus based complementary electronics.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Routing of Complex Contagion in Kleinberg's Small-World Networks

In Kleinberg's small-world network model, strong ties are modeled as deterministic edges in the underlying base grid and weak ties are modeled as random edges connecting remote nodes. The probability of connecting a node $u$ with node $v$ through a weak tie is proportional to $1/|uv|^α$, where $|uv|$ is the grid distance between $u$ and $v$ and $α\ge 0$ is the parameter of the model. Complex contagion refers to the propagation mechanism in a network where each node is activated only after $k \ge 2$ neighbors of the node are activated. In this paper, we propose the concept of routing of complex contagion (or complex routing), where we can activate one node at one time step with the goal of activating the targeted node in the end. We consider decentralized routing scheme where only the weak ties from the activated nodes are revealed. We study the routing time of complex contagion and compare the result with simple routing and complex diffusion (the diffusion of complex contagion, where all nodes that could be activated are activated immediately in the same step with the goal of activating all nodes in the end). We show that for decentralized complex routing, the routing time is lower bounded by a polynomial in $n$ (the number of nodes in the network) for all range of $α$ both in expectation and with high probability (in particular, $Ω(n^{\frac{1}{α+2}})$ for $α\le 2$ and $Ω(n^{\fracα{2(α+2)}})$ for $α> 2$ in expectation), while the routing time of simple contagion has polylogarithmic upper bound when $α= 2$. Our results indicate that complex routing is harder than complex diffusion and the routing time of complex contagion differs exponentially compared to simple contagion at sweetspot.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Computing the Least-core and Nucleolus for Threshold Cardinality Matching Games

Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. \emph{Core}, \emph{least-core} and \emph{nucleolus} are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues on the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph $G=(V,E)$ and a threshold $T$, in which the player set is $V$ and the profit of a coalition $S\subseteq V$ is 1 if the size of a maximum matching in $G[S]$ meets or exceeds $T$, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial time solvable. We also provide a general characterization of the least core for a large class of TCMG. Next, based on Gallai-Edmonds Decomposition in matching theory, we give a concise formulation of the nucleolus for a typical case of TCMG which the threshold $T$ equals $1$. When the threshold $T$ is relevant to the input size, we prove that the nucleolus can be obtained in polynomial time in bipartite graphs and graphs with a perfect matching.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

How to select the largest k elements from evolving data?

In this paper we investigate the top-$k$-selection problem, i.e. determine the largest, second largest, ..., and the $k$-th largest elements, in the dynamic data model. In this model the order of elements evolves dynamically over time. In each time step the algorithm can only probe the changes of data by comparing a pair of elements. Previously only two special cases were studied[2]: finding the largest element and the median; and sorting all elements. This paper systematically deals with $k\in [n]$ and solves the problem almost completely. Specifically, we identify a critical point $k^*$ such that the top-$k$-selection problem can be solved error-free with probability $1-o(1)$ if and only if $k=o(k^*)$. A lower bound of the error when $k=Ω(k^*)$ is also determined, which actually is tight under some condition. On the other hand, it is shown that the top-$k$-set problem, which means finding the largest $k$ elements without sorting them, can be solved error-free for all $k\in [n]$. Additionally, we extend the dynamic data model and show that most of these results still hold.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network

A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size so that with a guaranteed probability the number of users discussing the topic would reach a given threshold. We formulate the task as an optimization problem called seed minimization with probabilistic coverage guarantee (SM-PCG). This problem departs from the previous studies on social influence maximization or seed minimization because it considers influence coverage with probabilistic guarantees instead of guarantees on expected influence coverage. We show that the problem is not submodular, and thus is harder than previously studied problems based on submodular function optimization. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. The multiplicative ratio is tight while the additive error would be small if influence coverage distributions of certain seed sets are well concentrated. For one-way bipartite graphs we analytically prove the concentration condition and obtain an approximation algorithm with an $O(\log n)$ multiplicative ratio and an $O(\sqrt{n})$ additive error, where $n$ is the total number of nodes in the social graph. Moreover, we empirically verify the concentration condition in real-world networks and experimentally demonstrate the effectiveness of our proposed algorithm comparing to commonly adopted benchmark algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol

The classical secretary problem investigates the question of how to hire the best secretary from $n$ candidates who come in a uniformly random order. In this work we investigate a parallel generalizations of this problem introduced by Feldman and Tennenholtz [14]. We call it shared $Q$-queue $J$-choice $K$-best secretary problem. In this problem, $n$ candidates are evenly distributed into $Q$ queues, and instead of hiring the best one, the employer wants to hire $J$ candidates among the best $K$ persons. The $J$ quotas are shared by all queues. This problem is a generalized version of $J$-choice $K$-best problem which has been extensively studied and it has more practical value as it characterizes the parallel situation. Although a few of works have been done about this generalization, to the best of our knowledge, no optimal deterministic protocol was known with general $Q$ queues. In this paper, we provide an optimal deterministic protocol for this problem. The protocol is in the same style of the $1\over e$-solution for the classical secretary problem, but with multiple phases and adaptive criteria. Our protocol is very simple and efficient, and we show that several generalizations, such as the fractional $J$-choice $K$-best secretary problem and exclusive $Q$-queue $J$-choice $K$-best secretary problem, can be solved optimally by this protocol with slight modification and the latter one solves an open problem of Feldman and Tennenholtz [14]. In addition, we provide theoretical analysis for two typical cases, including the 1-queue 1-choice $K$-best problem and the shared 2-queue 2-choice 2-best problem. For the former, we prove a lower bound $1-O(\frac{\ln^2K}{K^2})$ of the competitive ratio. For the latter, we show the optimal competitive ratio is $\approx0.372$ while previously the best known result is 0.356 [14].

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The far-zone interatomic Casimir-Polder potential between two ground-state atoms outside a Schwarzschild black hole

Based on the idea that the vacuum fluctuations of electromagnetic fields can induce instantaneous correlated dipoles, we study the far-zone Casimir-Polder potential between two atoms in the Boulware, Unruh and Hartle-Hawking vacua outside a Schwarzschild black hole. We show that, at spatial infinity, the Casimir-Polder potential in the Boulware vacuum is similar to that in the Minkowski vacuum in flat spacetime with a behavior of $R^{-7}$, so is in the Unruh vacuum as a result of the backscattering of the Hawking radiation from the black hole off the spacetime curvature. However, the interatomic Casimir-Polder potential in the Hartle-Hawking vacuum behaves like that in a thermal bath at the Hawking temperature. In the region near the event horizon of the black hole, the modifications caused by the space-time curvature make the interatomic Casimir-Polder potential smaller in all three vacuum states.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rotational constants of multi-phonon bands in an effective theory for deformed nuclei

We consider deformed nuclei within an effective theory that exploits the small ratio between rotational and vibrational excitations. For even-even nuclei, the effective theory predicts small changes in the rotational constants of bands built on multi-phonon excitations that are linear in the number of excited phonons. In 166Er and 168Er, this explains the main variations of the rotational constants of the two-phonon gamma vibrational bands. In 232Th, the effective theory correctly explains the trend that the rotational constants decrease with increasing spin of the band head. We also study the effective theory for deformed odd nuclei. Here, time-odd terms enter the Lagrangian and generate effective magnetic forces that yield the high level densities observed in such nuclei.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Consensus Resilient to Both Crash Failures and Strategic Manipulations

In this paper, we study distributed consensus in synchronous systems subject to both unexpected crash failures and strategic manipulations by rational agents in the system. We adapt the concept of collusion-resistant Nash equilibrium to model protocols that are resilient to both crash failures and strategic manipulations of a group of colluding agents. For a system with $n$ distributed agents, we design a deterministic protocol that tolerates 2 colluding agents and a randomized protocol that tolerates $n - 1$ colluding agents, and both tolerate any number of failures. We also show that if colluders are allowed an extra communication round after each synchronous round, there is no protocol that can tolerate even 2 colluding agents and 1 crash failure.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Casimir-Polder-like force on an atom outside a Schwarzschild black hole

We calculate, in the framework of open quantum systems, the ground state energy-level shift for a static two-level atom outside a spherically symmetric black hole in interaction with fluctuating massless scalar fields in the Boulware and Unruh vacuums. We find that the energy-level shift is position-dependent and thus gives rise to a force on the atom besides the classical gravitational force. For the case of the Boulware vacuum which represents a star that has not collapsed through its event horizon, this force is attractive near the horizon and is repulsive far away from the black hole with a behavior of $r^{-3}$ . For the case of the Unruh vacuum which represents a radiating black hole, we find that the contribution to the Casimir-Polder-like force due to the presence of Hawking radiation is always attractive and, remarkably, this attractive force diverges at the event horizon.

0 citations0 reviewsNo code linkedOpen access