26838 research outputs found
Sort by
Jacques Benders and his decomposition algorithm
Get PDFBenders is a household name in optimization, but as a person he was hardly known beyond his circle of colleagues and students. In this brief paper, we review his life and work
The Book of Doublends Jined: Parsing Finnegans Wake with ixml
Get PDF'Finnegans Wake' by James Joyce is probably the hardest book to read in the English language. A principle hurdle is the length and convolutedness of the sentences. This paper reports work-in-progress of an attempt to handle the complexity of 'Finnegans Wake' by parsing the sentences (at a structural, not a semantic level), to reveal their top-level structure. It takes the reader step-by-step through the construction of an ixml grammar for dealing with one chapter of the book
Affective user interfaces
No full textAffective user interfaces are interfaces that are capable of eliciting, conveying, modeling, enhancing, or influencing emotions in their user. This chapter summarizes the role user affect plays in interface design, including how it can best be understood and represented, and the variety of methods pertaining to its analysis and display. Drawing on the state of the art and history of affective interfaces, we highlight how such interfaces can be used to enhance existing computer-mediated communication to make them more engaging and more natural, as well as to enable new interaction possibilities. Specifically, we focus on: (1) augmenting computer-mediated communication with affect, (2) digital emotion regulation and support, (3) affective immersive experiences, (4) affective haptics, and (5) persuasive interfaces. Finally, we consider the risks of these technologies, including ethical aspects (e.g., emotion surveillance, ground truth reliability, and bias), as well as the opportunities for such interfaces, from affective embodied agents designed for health and positive behavior changes, to affective learning and education, and to artistic creations
Learning and decision-making with data : Optimal formulations and phase transitions
No full textWe study the problem of designing optimal learning and decision-making formulations when only historical data is available. Prior work typically commits to a particular class of data-driven formulation and subsequently tries to establish out-of-sample performance guarantees. Following (Van Parys et al. From data to decisions: Distributionally robust optimization is optimal. Management Science 2020) we take here the opposite approach. We define first a sensible yardstick with which to measure the quality of any data-driven formulation and subsequently seek to find an “optimal” such formulation. Informally, any data-driven formulation can be seen to balance a measure of proximity of the estimated cost to the actual cost while guaranteeing a level of out-of-sample performance. Given an acceptable level of out-of-sample performance, we construct explicitly a data-driven formulation that is uniformly closer to the true cost than any other formulation enjoying the same out-of-sample performance. We show the existence of three distinct out-of-sample performance regimes; a superexponential regime, an exponential regime, and a subexponential regime. The optimal data-driven formulations can be interpreted as a classically robust formulation in the superexponential regime, an entropic distributionally robust formulation in the exponential regime, and finally a variance penalized formulation in the subexponential regime. This final observation unveils a surprising connection between these three, at first glance seemingly unrelated, data-driven formulations which until now remained hidden
The compressed oracle is a worthy (multiplicative) adversary
Get PDFThe compressed oracle technique, introduced in the context of quantum cryptanalysis, is the latest method for proving quantum query lower bounds, and has had an impressive number of applications since its introduction, due in part to the ease of importing classical lower bound intuition into the quantum setting via this method. Previously, the main quantum query lower bound methods were the polynomial method, the adversary method, and the multiplicative adversary method, and their relative powers were well understood. In this work, we situate the compressed oracle technique within this established landscape, by showing that it is a special case of the multiplicative adversary method. To accomplish this, we introduce a simplified restriction of the multiplicative adversary method, the MLADV method, that remains powerful enough to capture the polynomial method and exhibit a strong direct product theorem, but is much simpler to reason about. We show that the compressed oracle technique is also captured by the MLADV method. This might make the MLADV method a promising direction in the current quest to extend the compressed oracle technique to non-product distributions
Random regular graph states are complex at almost any depth
Get PDFGraph states are fundamental objects in the theory of quantum information due to their simple classical description and rich entanglement structure. They are also intimately related to instantaneous quantum polynomial-time (IQP) circuits, which have applications in quantum pseudorandomness and quantum advantage. For us, they are a toy model to understand the relation between circuit connectivity, entanglement structure, and computational complexity. In the worst case, a strict dichotomy in the computational universality of such graph states appears as a function of the degree of a regular graph state [Ghosh et al., Phys. Rev. Lett. 131, 030601 (2023)]. In this paper, we study the average-case complexity of simulating random graph states of varying degree when measured in random product bases and give distinct evidence that a similar complexity-theoretic dichotomy exists in the average case. Specifically, we consider random -regular graph states and prove three distinct results: First, we show two families of IQP circuits of depth and show that they anticoncentrate for any when measured in a random plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime with , we prove that random -regular graph states contain polynomially large grid graphs as induced subgraphs with high probability. This implies that they are universal resource states for measurement-based computation. Third, in the regime of high degree , we show that random graph states are not sufficiently entangled to be trivially classically simulable, unlike Haar-random states. Proving the three results requires different techniques—the analysis of a classical statistical-mechanics model using Krawtchouck polynomials, graph-theoretic analysis using the switching method, and analysis of the ranks of submatrices of random adjacency matrices, respectively
Classifications of open-domain queries for tabular data analysis
No full textThis repository contains the code, prompts, and data used to build and evaluate the classifiers presented in the paper "Are We Asking the Right Questions? On Ambiguity in Natural Language Queries for Tabular Data Analysis". The work was accepted to the AI for Tabular Data workshop at EurIPS 2025
