26838 research outputs found
Sort by
Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs
Get PDFIn this paper, we investigate the distribution of zeros of the independence polynomial of hypergraphs of maximum degree (Formula presented.). For graphs, the largest zero-free disk around zero was described by Shearer as having radius (Formula presented.). Recently, it was shown by Galvin et al. that for hypergraphs the disk of radius (Formula presented.) is zero-free; however, it was conjectured that the actual truth should be (Formula presented.). We show that this is indeed the case. We also show that there exists an open region around the interval (Formula presented.) that is zero-free for hypergraphs of maximum degree (Formula presented.), which extends the result of Peters and Regts from graphs to hypergraphs. Finally, we determine the radius of the largest zero-free disk for the family of bounded degree (Formula presented.) -uniform linear hypertrees in terms of (Formula presented.) and (Formula presented.)
XGBoostPP: Tree-based estimation of point process intensity functions
Get PDFMedium-sized point pattern data arises in many applications, however, their analyses have been overlooked in the machine learning community. In this paper, we propose a novel tree-based ensemble method, named XGBoostPP, to nonparametrically estimate the intensity of a point process as a function of covariates. It extends the use of gradient-boosted regression trees (Chen and Guestrin, 2016) to the point process literature via two carefully designed loss functions. The first loss is based on the Poisson likelihood and works for general point processes. The second loss derives from a weighted likelihood, where spatially dependent weights are dynamically computed and incorporated to further improve the estimation efficiency for clustered point processes. An efficient learning algorithm and an associated validation procedure are developed for model estimation, and the effectiveness of the proposed method is demonstrated through extensive simulation studies and two real data analyses. In particular, we report that XGBoostPP achieves superior performance to state-of-the-art approaches, showcasing the advantages of using tree ensembles to estimate complex intensity functions for medium-sized point patterns
Game-theoretical modeling of sequential topology attacks in radially operated distribution networks
Get PDFWhile the digitalization of the power system has its merit, it also introduced emerging cyber attack threats. Once the attacker has access to the control of the system, they can cause significant damage to infrastructure and society as a whole. Game-theoretical models that allow the decision-making of multiple actors have been previously studied to assess the impact of such attacks and potential responses. In this study, we present a novel and generalized incident response game against topology attacks in radially operated distribution networks. The introduced model allows for sequential interactions between the attacker and defender over multiple waves of attacks. Within this new framework, we propose a simplified model called the associated single-round game to efficiently compute the lower-bound load loss attainable by the adversary. Finally, a case study on the IEEE 33-bus system showed that the multi-round game framework can be used to determine and compare optimal sequences of actions. Moreover, the single-round game required less computation while achieving the same maximum loss by the attacker against an optimal defender, indicating a tight bound
Partial allocations in budget-feasible mechanism design: Bridging multiple levels of service and divisible agents
Get PDFBudget-feasible procurement has been a major paradigm in mechanism design since its introduction by Singer [28]. An auctioneer (buyer) with a strict budget constraint is interested in buying goods or services from a group of strategic agents (sellers). In many scenarios, it makes sense to allow the auctioneer to only partially buy what an agent offers, e.g., an agent might have multiple copies of an item to sell, might offer multiple levels of a service, or may be available to perform a task for any fraction of a specified time interval. Nevertheless, the focus of the related literature has been on settings in which each agent's services are either fully acquired or not at all. A reason for this is that in settings with partial allocations, such as the ones mentioned, there are strong inapproximability results (see, e.g., Anari et al. [5], Chan and Chen [10]). Under the mild assumption of being able to afford each agent entirely, we are able to circumvent such results. We design a polynomial-time, deterministic, truthful, budget-feasible, (2+√3)-approximation mechanism for the setting in which each agent offers multiple levels of service and the auctioneer has a valuation function that is separable concave, i.e., it is the sum of concave functions. We then use this result to design a deterministic, truthful, and budget-feasible O(1)-approximation mechanism for the setting in which any fraction of a service can be acquired, again for separable concave objectives. For the special case in which the objective is the sum of linear valuation functions, we improve the best known approximation ratio for the problem from (by Klumper and Schäfer [19]) to (3+√5)/2. This establishes a separation between this setting and its indivisible counterpart
Hide-and-Seek and the non-resignability of the BUFF transform
No full textThe BUFF transform, due to Cremers et al. (S&P’21), is a generic transformation for digital signature scheme, with the purpose of obtaining additional security guarantees beyond unforgeability: exclusive ownership, message-bound signatures, and non-resignability. Non-resignability (which essentially challenges an adversary to re-sign an unknown message for which it only obtains the signature) turned out to be a delicate matter, as recently Don et al. (CRYPTO’24) showed that the initial definition is essentially unachievable; in particular, it is not achieved by the BUFF transform. This led to the introduction of new, weakened versions of non-resignability, which are (potentially) achievable. In particular, it was shown that a salted variant of the BUFF transform does achieves some weakened version of non-resignability. However, the salting requires additional randomness and leads to slightly larger signatures. Whether the original BUFF transform also achieves some meaningful notion of non-resignability remained a natural open question. In this work, we answer this question in the affirmative. We show that the BUFF transform satisfies the (almost) strongest notions of non-resignability one can hope for, facing the known impossibility results. Our results cover both the statistical and the computational case, and both the classical and the quantum setting. At the core of our analysis lies a new security game for random oracles that we call Hide-and-Seek. While seemingly innocent at first glance, it turns out to be surprisingly challenging to rigorously analyze
Classifying fermionic states via many-body correlation measures
Get PDFUnderstanding the structure of quantum correlations in a many-body system is key to its computational treatment. For fermionic systems, correlations can be defined as deviations from Slater determinant states. The link between fermionic correlations and efficient computational physics methods is actively studied but remains ambiguous. We make progress in establishing this connection mathematically. In particular, we find a rigorous classification of states relative to k-fermion correlations, which admits a computational physics interpretation. Correlations are captured by a measure ωk, a function of k-fermion reduced density matrix that we call twisted purity. A condition ωk = 0 for a given k puts the state in a class Gk of correlated states. Sets Gk are nested in k, and Slater determinants correspond to k = 1. Classes Gk=O(1) are shown to be physically relevant, as ωk vanishes or nearly vanishes for truncated configuration-interaction states, perturbation series around Slater determinants, and some nonperturbative eigenstates of the 1D Hubbard model. For each k = O(1), we give an explicit ansatz with a polynomial number of parameters that covers all states in Gk. Potential applications of this ansatz and its connections to the coupled-cluster wavefunction are discussed
Breaking XOR arbiter PUFs with chosen challenge attack
Get PDFThe XOR Arbiter PUF was introduced as a strong PUF in 2007 and was broken in 2015 by a Machine Learning (ML) attack, which allows the underlying Arbiter PUFs to be modeled individually by exploiting reliability information of the measured responses. To mitigate the reliability-based attacks, state-of-the-art understanding shows that the reliability of individual Arbiter PUFs and the overall XOR Arbiter PUF can be boosted to an arbitrarily high level, thus rendering all known reliability-based ML attacks infeasible; alternatively, an access control interface around the XOR Arbiter PUF can prevent the same challenge-response pairs from being accessed repeatedly, thus eliminating the leakage of reliability information. We show that, for the first time, a perfectly reliable XOR Arbiter PUF can be successfully attacked in a divide-and-conquer manner, meaning each underlying Arbiter PUF in an XOR Arbiter PUF can be attacked individually. This allows us to attack large XOR Arbiter PUFs efficiently, even without reliability information or any side-channel information. Our key insight is that, instead of reliability information, the responses of highly correlated challenges also reveal how close the responses are to the response decision boundary. This leads to a chosen challenge attack on XOR Arbiter PUFs by carefully choosing correlated challenges to measure and aggregate the collected information. We validate our attack by using PUF simulation, as well as an XOR Arbiter PUF implemented on FPGA. We also demonstrate that our chosen challenge methodology is compatible with the state-of-the-art combined gradient-based multi-objective optimization attack. Finally, we discuss an effective countermeasure that can prevent our attack but with a relatively large area overhead compared to the PUF itself
Lower bounds for unitary property testing with proofs and advice
Get PDFIn unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any C-tester with C ⊆ QMA(2)/qpoly, showing that even having access to both (unentangled) quantum proofs and quantum advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which QMA(2) ⊅ SBQP and QMA/qpoly ⊅ SBQP. The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision
A better linear unbiased estimator for averages over discrete structures
No full textGiven an i.i.d. sample drawn from some probability distribution on a finite set, the best (in the sense of least variance) linear unbiased estimator (BLUE) of the average of any quantity with respect to that distribution is the sample average of the quantity. Here we consider the situation in which, together with the sample, also the probability mass (possibly unnormalized) at each sample point is provided. We show that with that information BLUE can be systematically improved. The proposed procedure is expected to have applications in statistical physics, where it is common to have a closed-form specification of the relevant (unnormalized) probability distribution
Are we asking the right questions? On ambiguity in natural language queries for tabular data analysis
Get PDFNatural language interfaces to tabular data must handle ambiguities inherent to queries. Instead of treating ambiguity as a deficiency, we reframe it as a feature of cooperative interaction where users are intentional about the degree to which they specify queries. We develop a principled framework based on a shared responsibility of query specification between user and system, distinguishing unambiguous and ambiguous cooperative queries, which systems can resolve through reasonable inference, from uncooperative queries that cannot be resolved. Applying the framework to evaluations for tabular question answering and analysis, we analyze the queries in 15 popular datasets, and observe an uncontrolled mixing of query types neither adequate for evaluating a system's execution accuracy nor for evaluating interpretation capabilities. This conceptualization around cooperation in resolving queries informs how to design and evaluate natural language interfaces for tabular data analysis, for which we distill concrete directions for future research and broader implications