Search

Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of preferences, ordinal rankings are often the only available information due to their simplicity and practical constraints. The metric distortion framework addresses this issue by modeling voters and candidates as points in a metric space, with distortion quantifying the efficiency loss from relying solely on ordinal rankings. Existing works define the cost of a voter with respect to a candidate as their distance and set the overall cost as either the sum (utilitarian) or maximum (egalitarian) of these costs across all voters. They show that deterministic algorithms achieve a best-possible distortion of 3 for any metric when considering a single candidate. This paper explores whether one can obtain a better approximation compared to an optimal candidate by relying on a committee of $k$ candidates ($k \ge 1$), where the cost of a voter is defined as its distance to the closest candidate in the committee. We answer this affirmatively in the case of line metrics, demonstrating that with $O(1)$ candidates, it is possible to achieve optimal cost. Our results extend to both utilitarian and egalitarian objectives, providing new upper bounds for the problem. We complement our results with lower bounds for both the line and 2-D Euclidean metrics.

We consider two-dimensional $(\lambda_1, \lambda_2)$-constacyclic codes over $\mathbb{F}_{q}$ of area $M N$, where $q$ is some power of prime $p$ with $\gcd(M,p)=1$ and $\gcd(N,p)=1$. With the help of common zero (CZ) set, we characterize 2-D constacyclic codes. Further, we provide an algorithm to construct an ideal basis of these codes by using their essential common zero (ECZ) sets. We describe the dual of 2-D constacyclic codes. Finally, we provide an encoding scheme for generating 2-D constacyclic codes. We present an example to illustrate that 2-D constacyclic codes can have better minimum distance compared to their cyclic counterparts with the same code size and code rate., Comment: 23 pages

Second-order methods are widely adopted to improve the convergence rate of learning algorithms. In federated learning (FL), these methods require the clients to share their local Hessian matrices with the parameter server (PS), which comes at a prohibitive communication cost. A classical solution to this issue is to approximate the global Hessian matrix from the first-order information. Unlike in idealized networks, this solution does not perform effectively in over-the-air FL settings, where the PS receives noisy versions of the local gradients. This paper introduces a novel second-order FL framework tailored for wireless channels. The pivotal innovation lies in the PS's capability to directly estimate the global Hessian matrix from the received noisy local gradients via a non-parametric method: the PS models the unknown Hessian matrix as a Gaussian process, and then uses the temporal relation between the gradients and Hessian along with the channel model to find a stochastic estimator for the global Hessian matrix. We refer to this method as Gaussian process-based Hessian modeling for wireless FL (GP-FL) and show that it exhibits a linear-quadratic convergence rate. Numerical experiments on various datasets demonstrate that GP-FL outperforms all classical baseline first and second order FL approaches., Comment: The paper is submitted to IEEE Transactions on Signal Processing

This study introduces a novel methodology for managing train network disruptions across the entire rail network, leveraging digital tools and methodologies. The approach involves two stages, taking into account possible and practical features such as allowing trains to occupy opposite tracks and considering infrastructure capacity for train stops. In the first stage, important nodes within the train network are identified, considering both a topological feature and passenger demand. Subsequently, the network is aggregated based on these important nodes, employing a digital approach to reduce problem complexity. In the second stage, we develop an Integer Programming model for train rescheduling. We then solve this model using the CPLEX solver to evaluate its efficiency. The first case study applies this methodology to the Iranian railway, which is known as a sparse rail network. The results show minimal deviation from the initial train timetable due to the low frequency of trips in each block. Although the approach successfully addresses the train rescheduling problem for various disruption scenarios on the Iranian railway, the excessive computational time required by the optimization model prompts us to make adjustments. Finally, the second case study demonstrates the implementation of the adjusted model in a busy test network. This adaptation significantly reduces computational time by up to 88%. It can be effectively utilized for disruption management in busy networks, where trains need to receive a secondary timetable promptly when facing disruptions.

We investigate the thermodynamic limits on scaling fault-tolerant quantum computers due to heating from quantum error correction (QEC). Quantum computers require error correction, which accounts for 99.9% of the qubit demand and generates heat through information-erasing processes. This heating increases the error rate, necessitating more rounds of error correction. We introduce a dynamical model that characterizes heat generation and dissipation for arrays of qubits weakly coupled to a refrigerator and identify a dynamical phase transition between two operational regimes: a bounded-error phase, where temperature stabilizes and error rates remain below fault-tolerance thresholds, and an unbounded-error phase, where rising temperatures drive error rates beyond sustainable levels, making fault tolerance infeasible. Applying our model to a superconducting qubit system performing Shor's algorithm to factor 2048-bit RSA integers, we find that current experimental parameters place the system in the bounded-error phase. Our results indicate that, while inherent heating can become significant, this thermodynamic constraint should not limit scalable fault tolerance if current hardware capabilities are maintained as systems scale., Comment: 8 pages, 7 figures

Large language models (LLMs) are known to exhibit demographic biases, yet few studies systematically evaluate these biases across multiple datasets or account for confounding factors. In this work, we examine LLM alignment with human annotations in five offensive language datasets, comprising approximately 220K annotations. Our findings reveal that while demographic traits, particularly race, influence alignment, these effects are inconsistent across datasets and often entangled with other factors. Confounders -- such as document difficulty, annotator sensitivity, and within-group agreement -- account for more variation in alignment patterns than demographic traits alone. Specifically, alignment increases with higher annotator sensitivity and group agreement, while greater document difficulty corresponds to reduced alignment. Our results underscore the importance of multi-dataset analyses and confounder-aware methodologies in developing robust measures of demographic bias in LLMs.

Large Language Models (LLMs) have shown potential to enhance software development through automated code generation and refactoring, reducing development time and improving code quality. This study empirically evaluates StarCoder2, an LLM optimized for code generation, in refactoring code across 30 open-source Java projects. We compare StarCoder2's performance against human developers, focusing on (1) code quality improvements, (2) types and effectiveness of refactorings, and (3) enhancements through one-shot and chain-of-thought prompting. Our results indicate that StarCoder2 reduces code smells by 20.1% more than developers, excelling in systematic issues like Long Statement and Magic Number, while developers handle complex, context-dependent issues better. One-shot prompting increases the unit test pass rate by 6.15% and improves code smell reduction by 3.52%. Generating five refactorings per input further increases the pass rate by 28.8%, suggesting that combining one-shot prompting with multiple refactorings optimizes performance. These findings provide insights into StarCoder2's potential and best practices for integrating LLMs into software refactoring, supporting more efficient and effective code improvement in real-world applications.

Humans have the ability to reason about geometric patterns in images and scenes from a young age. However, developing large multimodal models (LMMs) capable of similar reasoning remains a challenge, highlighting the need for robust evaluation methods to assess these capabilities. We introduce TurtleBench, a benchmark designed to evaluate LMMs' capacity to interpret geometric patterns -- given visual examples, textual instructions, or both -- and generate precise code outputs. Inspired by turtle geometry, a notion used to teach children foundational coding and geometric concepts, TurtleBench features tasks with patterned shapes that have underlying algorithmic logic. Our evaluation reveals that leading LMMs struggle significantly with these tasks, with GPT-4o achieving only 19\% accuracy on the simplest tasks and few-shot prompting only marginally improves their performance ($<2\%$). TurtleBench highlights the gap between human and AI performance in intuitive and visual geometrical understanding, setting the stage for future research in this area. TurtleBench stands as one of the few benchmarks to evaluate the integration of visual understanding and code generation capabilities in LMMs, setting the stage for future research. Code and Dataset for this paper is provided here: https://github.com/sinaris76/TurtleBench

The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertices (agents). However, little attention has been given to the concept of class fairness, where agents are categorized into different classes, and the matching algorithm must ensure equitable distribution across these classes. We here focus on randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution is the first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$ approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent approximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for $\alpha > 0.761$. In a similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates a nearly tight CEF approximation. Lastly, we define the ``price of fairness,'' which represents the trade-off between optimal and fair matching. We demonstrate that increasing the level of fairness in the approximation of the solution leads to a decrease in the objective of maximizing USW, following an inverse proportionality relationship., Comment: Accepted to NeurIPS 2024

At millimeter wavelengths, the atmospheric emission is circularly polarized owing to the Zeeman splitting of molecular oxygen by the Earth's magnetic field. We report a measurement of the signal in the 150 GHz band using 3 years of observations of the \textsc{Polarbear} project. Although the detectors are sensitive to linear polarization, we can measure the circular polarization because a continuously rotating half-wave plate in the optics converts part of circular polarization into linear polarization. The atmospheric circular polarization signal appears as a modulated signal at twice the frequency of rotation of the half-wave plate. We reconstruct the azimuthal gradient of the circular polarization signal and measure the dependencies on the scanning azimuth and the detector bandpass. We compare the signal with a simulation based on atmospheric emission theory, the detector bandpass, and the half-wave plate leakage spectrum model. We find the ratio of the observed azimuthal slope to the simulated slope is $0.92 \pm 0.01\rm{(stat)} \pm 0.07\rm{(sys)}$, which demonstrates that our measurement is consistent with theoretical prediction. This result validates our understanding of the instrument and reinforces the feasibility of measuring the circular polarization using the imperfection of the half-wave plate. Quantifying atmospheric circular polarization is the first step toward conducting a search for cosmological circular polarization at these wavelengths., Comment: 22 pages, 11 figures

Optimally designing molten salt applications requires knowledge of their thermophysical properties, but existing databases are incomplete, and experiments are challenging. Ideal mixing and Redlich-Kister models are computationally cheap but lack either accuracy or generality. To address this, a transfer learning approach using deep neural networks (DNNs) is proposed, combining Redlich-Kister models, experimental data, and ab initio properties. The approach predicts molten salt density with high accuracy ($r^{2}$ > 0.99, MAPE < 1%), outperforming the alternatives., Comment: Manuscript contains 25 pages including references and other information. Manuscript contains 4 figures and 3 tables. To be submitted to ACS Journal of Chemical Theory and Computation

We consider deep deterministic policy gradient (DDPG) in the context of reinforcement learning with sparse rewards. To enhance exploration, we introduce a search procedure, \emph{${\epsilon}{t}$-greedy}, which generates exploratory options for exploring less-visited states. We prove that search using $\epsilon t$-greedy has polynomial sample complexity under mild MDP assumptions. To more efficiently use the information provided by rewarded transitions, we develop a new dual experience replay buffer framework, \emph{GDRB}, and implement \emph{longest n-step returns}. The resulting algorithm, \emph{ETGL-DDPG}, integrates all three techniques: \bm{$\epsilon t$}-greedy, \textbf{G}DRB, and \textbf{L}ongest $n$-step, into DDPG. We evaluate ETGL-DDPG on standard benchmarks and demonstrate that it outperforms DDPG, as well as other state-of-the-art methods, across all tested sparse-reward continuous environments. Ablation studies further highlight how each strategy individually enhances the performance of DDPG in this setting.

Integrating artificial intelligence into modern society is profoundly transformative, significantly enhancing productivity by streamlining various daily tasks. AI-driven recognition systems provide notable advantages in the food sector, including improved nutrient tracking, tackling food waste, and boosting food production and consumption efficiency. Accurate food classification is a crucial initial step in utilizing advanced AI models, as the effectiveness of this process directly influences the success of subsequent operations; therefore, achieving high accuracy at a reasonable speed is essential. Despite existing research efforts, a gap persists in improving performance while ensuring rapid processing times, prompting researchers to pursue cost-effective and precise models. This study addresses this gap by employing the state-of-the-art EfficientNetB7 architecture, enhanced through transfer learning, data augmentation, and the CBAM attention module. This methodology results in a robust model that surpasses previous studies in accuracy while maintaining rapid processing suitable for real-world applications. The Food11 dataset from Kaggle was utilized, comprising 16643 imbalanced images across 11 diverse classes with significant intra-category diversities and inter-category similarities. Furthermore, the proposed methodology, bolstered by various deep learning techniques, consistently achieves an impressive average accuracy of 96.40%. Notably, it can classify over 60 images within one second during inference on unseen data, demonstrating its ability to deliver high accuracy promptly. This underscores its potential for practical applications in accurate food classification and enhancing efficiency in subsequent processes., Comment: 20 pages, six figures, two tables

In tackling the challenges of large language model (LLM) performance for Text-to-SQL tasks, we introduce CHASE-SQL, a new framework that employs innovative strategies, using test-time compute in multi-agent modeling to improve candidate generation and selection. CHASE-SQL leverages LLMs' intrinsic knowledge to generate diverse and high-quality SQL candidates using different LLM generators with: (1) a divide-and-conquer method that decomposes complex queries into manageable sub-queries in a single LLM call; (2) chain-of-thought reasoning based on query execution plans, reflecting the steps a database engine takes during execution; and (3) a unique instance-aware synthetic example generation technique, which offers specific few-shot demonstrations tailored to test questions.To identify the best candidate, a selection agent is employed to rank the candidates through pairwise comparisons with a fine-tuned binary-candidates selection LLM. This selection approach has been demonstrated to be more robust over alternatives. The proposed generators-selector framework not only enhances the quality and diversity of SQL queries but also outperforms previous methods. Overall, our proposed CHASE-SQL achieves the state-of-the-art execution accuracy of 73.0% and 73.01% on the test set and development set of the notable BIRD Text-to-SQL dataset benchmark, rendering CHASE-SQL the top submission of the leaderboard (at the time of paper submission).

An algorithm for a family of self-starting high-order implicit time integration schemes with controllable numerical dissipation is proposed for both linear and nonlinear transient problems. This work builds on the previous works of the authors on elastodynamics by presenting a new algorithm that eliminates the need for factorization of the mass matrix providing benefit for the solution of nonlinear problems. The improved algorithm directly obtains the acceleration at the same order of accuracy of the displacement and velocity using vector operations (without additional equation solutions). The nonlinearity is handled by numerical integration within a time step to achieve the desired order of accuracy. The new algorithm fully retains the desirable features of the previous works: 1. The order of accuracy is not affected by the presence of external forces and physical damping; 2. numerical dissipation in the algorithm is controlled by a user-specified parameter, leading to schemes ranging from perfectly nondissipative A-stable to L-stable; 3. The effective stiffness matrix is a linear combination of the mass, damping, and stiffness matrices as in the trapezoidal rule. The proposed algorithm is shown to replicate the numerical results demonstrated on linear problems in previous works. Additional numerical examples of linear and nonlinear vibration and wave propagation are presented herein. Notably, the proposed algorithms show the same convergence rates for nonlinear problems as linear problems, and very high accuracy. Second-order time integration methods commonly used in commercial software produce significantly polluted acceleration responses for a common class of wave propagation problems. The high-order time integration schemes presented here perform noticably better at suppressing spurious high-frequency oscillations and producing reliable and useable acceleration responses., Comment: 50 pages, 31 figures, 93 equations. Source code available at https://github.com/ChongminSong/HighOrderTimeIngt_PartialFraction.git

Cell-free integrated sensing and communication (CF-ISAC) systems are just emerging as an interesting technique for future communications. Such a system comprises several multiple-antenna access points (APs), serving multiple single-antenna communication users and sensing targets. However, efficient beamforming designs that achieve high precision and robust performance in densely populated networks are lacking. This paper proposes a new beamforming algorithm by exploiting the inherent Riemannian manifold structure. The aim is to maximize the communication sum rate while satisfying sensing beampattern gains and per AP transmit power constraints. To address this constrained optimization problem, a highly efficient augmented Lagrangian model-based iterative manifold optimization for CF-ISAC (ALMCI) algorithm is developed. This algorithm exploits the geometry of the proposed problem and uses a complex oblique manifold. Conventional convex-concave procedure (CCPA) and multidimensional complex quadratic transform (MCQT)-CSA algorithms are also developed as comparative benchmarks. The ALMCI algorithm significantly outperforms both of these. For example, with 16 APs having 12 antennas and 30 dBm transmit power each, our proposed ALMCI algorithm yields 22.7% and 6.7% sum rate gains over the CCPA and MCQT-CSA algorithms, respectively. In addition to improvement in communication capacity, the ALMCI algorithm achieves superior beamforming gains and reduced complexity., Comment: 13 pages, 13 figures, submitted to an IEEE Transactions Journal

Quantization is a common approach to mitigate the communication cost of federated learning (FL). In practice, the quantized local parameters are further encoded via an entropy coding technique, such as Huffman coding, for efficient data compression. In this case, the exact communication overhead is determined by the bit rate of the encoded gradients. Recognizing this fact, this work deviates from the existing approaches in the literature and develops a novel quantized FL framework, called \textbf{r}ate-\textbf{c}onstrained \textbf{fed}erated learning (RC-FED), in which the gradients are quantized subject to both fidelity and data rate constraints. We formulate this scheme, as a joint optimization in which the quantization distortion is minimized while the rate of encoded gradients is kept below a target threshold. This enables for a tunable trade-off between quantization distortion and communication cost. We analyze the convergence behavior of RC-FED, and show its superior performance against baseline quantized FL schemes on several datasets.

We report a proof-of-principle lattice QCD simulation of the electric and magnetic polarizabilities for a neutral pion in the four-point function method. The results are based on the same quenched Wilson ensembles on a $24^3\times 48$ lattice at $\beta=6.0$ with pion mass from 1100 to 370 MeV previously used for a charged pion. For electric polarizability, the results are largely consistent with those from the background field method and ChPT. In contrast, there are significant differences for magnetic polarizability among the four-point function method, the background field method, and ChPT. The situation points to the potentially important role of disconnected diagrams for a neutral pion. We elucidate a transparent quark decomposition in the four-point function method that can be used to shed light on the issue., Comment: 11 pages, 9 figures, 1 table. This version matches the one published in NPB in content. arXiv admin note: text overlap with arXiv:2307.08620

Computational models of human learning can play a significant role in enhancing our knowledge about nuances in theoretical and qualitative learning theories and frameworks. There are many existing frameworks in educational settings that have shown to be verified using empirical studies, but at times we find these theories make conflicting claims or recommendations for instruction. In this study, we propose a new computational model of human learning, Procedural ABICAP, that reconciles the ICAP, Knowledge-Learning-Instruction (KLI), and cognitive load theory (CLT) frameworks for learning procedural knowledge. ICAP assumes that constructive learning generally yields better learning outcomes, while theories such as KLI and CLT claim that this is not always true. We suppose that one reason for this may be that ICAP is primarily used for conceptual learning and is underspecified as a framework for thinking about procedural learning. We show how our computational model, both by design and through simulations, can be used to reconcile different results in the literature. More generally, we position our computational model as an executable theory of learning that can be used to simulate various educational settings.

We present a homotopic approach to solving challenging, optimization-based motion planning problems. The approach uses Homotopy Optimization, which, unlike standard continuation methods for solving homotopy problems, solves a sequence of constrained optimization problems rather than a sequence of nonlinear systems of equations. The insight behind our proposed algorithm is formulating the discovery of this sequence of optimization problems as a search problem in a multidimensional homotopy parameter space. Our proposed algorithm, the Probabilistic Homotopy Optimization algorithm, switches between solve and sample phases, using solutions to easy problems as initial guesses to more challenging problems. We analyze how our algorithm performs in the presence of common challenges to homotopy methods, such as bifurcation, folding, and disconnectedness of the homotopy solution manifold. Finally, we demonstrate its utility via a case study on two dynamic motion planning problems: the cart-pole and the MIT Humanoid., Comment: 8 pages, 9 Figures, 2 Tables, to appear in the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2024)

Determining the capacities of quantum channels is one of the fundamental problems of quantum information theory. This problem is extremely challenging and technically difficult, allowing only lower and upper bounds to be calculated for certain types of channels. In this paper, we prove that every quantum channel $\Lambda$ in arbitrary dimension, when contaminated by white noise in the form $\Lambda_x(\rho)=(1-x)\Lambda(\rho)+x\tr(\rho) \frac{I}{d}$, completely loses its capacity of transmitting quantum states when $x\geq \frac{1}{2}$, no matter what type of encoding and decoding is used. In other words, the quantum capacity of the channel vanishes in this region. To show this, we find a channel ${\cal N}_x$, which anti-degrades the depolarizing channel when $x\geq \frac{1}{2}$. We also find the quantum capacity of the complement of the depolarizing channel in closed form. Besides the erasure channel, this is the only example of a parameteric channel in arbitrary dimension for which the quantum capacity has been calculated in closed form.

Detecting vulnerabilities is vital for software security, yet deep learning-based vulnerability detectors (DLVD) face a data shortage, which limits their effectiveness. Data augmentation can potentially alleviate the data shortage, but augmenting vulnerable code is challenging and requires a generative solution that maintains vulnerability. Previous works have only focused on generating samples that contain single statements or specific types of vulnerabilities. Recently, large language models (LLMs) have been used to solve various code generation and comprehension tasks with inspiring results, especially when fused with retrieval augmented generation (RAG). Therefore, we propose VulScribeR, a novel LLM-based solution that leverages carefully curated prompt templates to augment vulnerable datasets. More specifically, we explore three strategies to augment both single and multi-statement vulnerabilities, with LLMs, namely Mutation, Injection, and Extension. Our extensive evaluation across three vulnerability datasets and DLVD models, using two LLMs, show that our approach beats two SOTA methods Vulgen and VGX, and Random Oversampling (ROS) by 27.48%, 27.93%, and 15.41% in f1-score with 5K generated vulnerable samples on average, and 53.84%, 54.10%, 69.90%, and 40.93% with 15K generated vulnerable samples. Our approach demonstrates its feasibility for large-scale data augmentation by generating 1K samples at as cheap as US$ 1.88., Comment: 13 pages, 6 figures, 5 tables, 3 prompt templates, 1 algorithm

Detection of Graphical User Interface (GUI) elements is a crucial task for automatic code generation from images and sketches, GUI testing, and GUI search. Recent studies have leveraged both old-fashioned and modern computer vision (CV) techniques. Oldfashioned methods utilize classic image processing algorithms (e.g. edge detection and contour detection) and modern methods use mature deep learning solutions for general object detection tasks. GUI element detection, however, is a domain-specific case of object detection, in which objects overlap more often, and are located very close to each other, plus the number of object classes is considerably lower, yet there are more objects in the images compared to natural images. Hence, the studies that have been carried out on comparing various object detection models, might not apply to GUI element detection. In this study, we evaluate the performance of the four most recent successful YOLO models for general object detection tasks on GUI element detection and investigate their accuracy performance in detecting various GUI elements.

In the last decade, an impressive increase in software adaptions has led to a surge in log data production, making manual log analysis impractical and establishing the necessity for automated methods. Conversely, most automated analysis tools include a component designed to separate log templates from their parameters, commonly referred to as a "log parser". This paper aims to introduce a new fast and accurate log parser, named "Tipping". Tipping combines rule-based tokenizers, interdependency token graphs, strongly connected components, and various techniques to ensure rapid, scalable, and precise log parsing. Furthermore, Tipping is parallelized and capable of running on multiple processing cores with close to linear efficiency. We evaluated Tipping against other state-of-the-art log parsers in terms of accuracy, performance, and the downstream task of anomaly detection. Accordingly, we found that Tipping outperformed existing methods in accuracy and performance in our evaluations. More in-depth, Tipping can parse 11 million lines of logs in less than 20 seconds on a laptop machine. Furthermore, we re-implemented a parallelized version of the past IpLom algorithm to demonstrate the effect of parallel processing, and it became the second-fastest parser. As logs keep growing in volume and complexity, the software engineering community needs to ensure automated log analysis tools keep up with the demand, being capable of efficiently handling massive volumes of logs with high accuracy. Tipping's robustness, versatility, efficiency, and scalability make it a viable tool for the modern automated log analysis task.

Optimization problems are pervasive in sectors from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than optimally by state-of-the art solvers because the expertise required to formulate and solve these problems limits the widespread adoption of optimization tools and techniques. We introduce a Large Language Model (LLM)-based system designed to formulate and solve (mixed integer) linear programming problems from their natural language descriptions. Our system is capable of developing mathematical models, writing and debugging solver code, evaluating the generated solutions, and improving efficiency and correctness of its model and code based on these evaluations. OptiMUS-0.3 utilizes a modular structure to process problems, allowing it to handle problems with long descriptions and complex data without long prompts. Experiments demonstrate that OptiMUS-0.3 outperforms existing state-of-the-art methods on easy datasets by more than 12% and on hard datasets (including a new dataset, NLP4LP, released with this paper that features long and complex problems) by more than 8%., Comment: This paper documents OptiMUS-0.3, improving on OptiMUS-0.1 (arXiv:2310.06116) and OptiMUS-0.2 (arXiv:2402.10172). arXiv admin note: text overlap with arXiv:2402.10172

Recently, it was shown that the role of the teacher in knowledge distillation (KD) is to provide the student with an estimate of the true Bayes conditional probability density (BCPD). Notably, the new findings propose that the student's error rate can be upper-bounded by the mean squared error (MSE) between the teacher's output and BCPD. Consequently, to enhance KD efficacy, the teacher should be trained such that its output is close to BCPD in MSE sense. This paper elucidates that training the teacher model with MSE loss equates to minimizing the MSE between its output and BCPD, aligning with its core responsibility of providing the student with a BCPD estimate closely resembling it in MSE terms. In this respect, through a comprehensive set of experiments, we demonstrate that substituting the conventional teacher trained with cross-entropy loss with one trained using MSE loss in state-of-the-art KD methods consistently boosts the student's accuracy, resulting in improvements of up to 2.6\%., Comment: The paper was accepted at ECCV2024

We characterize constacyclic codes in the spectral domain using the finite field Fourier transform (FFFT) and propose a reduced complexity method for the spectral-domain decoder. Further, we also consider repeated-root constacyclic codes and characterize them in terms of symmetric and asymmetric $q$-cyclotomic cosets. Using zero sets of classical self-orthogonal and dual-containing codes, we derive quantum error correcting codes (QECCs) for both constacyclic Bose-Chaudhuri-Hocquenghem (BCH) codes and repeated-root constacyclic codes. We provide some examples of QECCs derived from repeated-root constacyclic codes and show that constacyclic BCH codes are more efficient than repeated-root constacyclic codes. Finally, quantum encoders and decoders are also proposed in the transform domain for Calderbank-Shor-Steane CSS-based quantum codes. Since constacyclic codes are a generalization of cyclic codes with better minimum distance than cyclic codes with the same code parameters, the proposed results are practically useful., Comment: 40 pages, 2 figures

The rapid growth of the Internet, driven by social media, web browsing, and video streaming, has made images central to the Web experience, resulting in significant data transfer and increased webpage sizes. Traditional image compression methods, while reducing bandwidth, often degrade image quality. This paper explores a novel approach using generative AI to reconstruct images at the edge or client-side. We develop a framework that leverages text prompts and provides additional conditioning inputs like Canny edges and color palettes to a text-to-image model, achieving up to 99.8% bandwidth savings in the best cases and 92.6% on average, while maintaining high perceptual similarity. Empirical analysis and a user study show that our method preserves image meaning and structure more effectively than traditional compression methods, offering a promising solution for reducing bandwidth usage and improving Internet affordability with minimal degradation in image quality.

Recently, capacitive micromachined ultrasound transducers (CMUTs) with long rectangular membranes have demonstrated performance advantages over conventional piezoelectric transducers; however, modeling these CMUT geometries has been limited to computationally burdensome numerical methods. Improved fast modeling methods such as equivalent circuit models could help achieve designs with even better performance. The primary obstacle in developing such methods is the lack of tractable methods for computing the radiation impedance of clamped rectangular radiators. This paper presents a method which approximates the velocity profile using a polynomial shape model to rapidly and accurately estimate radiation impedance. The validity of the approximate velocity profile and corresponding radiation impedance calculation was assessed using finite element simulations for a variety of membrane aspect ratios and bias voltages. Our method was evaluated for rectangular radiators with width:length ratios from 1:1 up to 1:25. At all aspect ratios, the radiation resistance was closely modeled. However, when calculating the radiation reactance, our initial approach was only accurate for low aspect ratios. This motivated us to consider an alternative shape model for high aspect ratios, which was more accurate when compared with FEM. To facilitate development of future rectangular CMUTs, we provide a MATLAB script which quickly calculates radiation impedance using both methods., Comment: 18 pages, 10 figures, submitted to Sensors

The rise of deep learning has led to various successful attempts to apply deep neural networks (DNNs) for important networking tasks such as intrusion detection. Yet, running DNNs in the network control plane, as typically done in existing proposals, suffers from high latency that impedes the practicality of such approaches. This paper introduces NetNN, a novel DNN-based intrusion detection system that runs completely in the network data plane to achieve low latency. NetNN adopts raw packet information as input, avoiding complicated feature engineering. NetNN mimics the DNN dataflow execution by mapping DNN parts to a network of programmable switches, executing partial DNN computations on individual switches, and generating packets carrying intermediate execution results between these switches. We implement NetNN in P4 and demonstrate the feasibility of such an approach. Experimental results show that NetNN can improve the intrusion detection accuracy to 99\% while meeting the real-time requirement.

Task-orientated conversational agents interact with users and assist them via leveraging external APIs. A typical task-oriented conversational system can be broken down into three phases: external API selection, argument filling, and response generation. The focus of our work is the task of argument filling, which is in charge of accurately providing arguments required by the selected API. Upon comprehending the dialogue history and the pre-defined API schema, the argument filling task is expected to provide the external API with the necessary information to generate a desirable agent action. In this paper, we study the application of Large Language Models (LLMs) for the problem of API argument filling task. Our initial investigation reveals that LLMs require an additional grounding process to successfully perform argument filling, inspiring us to design training and prompting frameworks to ground their responses. Our experimental results demonstrate that when paired with proposed techniques, the argument filling performance of LLMs noticeably improves, paving a new way toward building an automated argument filling framework.

Conditional validity and length efficiency are two crucial aspects of conformal prediction (CP). Conditional validity ensures accurate uncertainty quantification for data subpopulations, while proper length efficiency ensures that the prediction sets remain informative. Despite significant efforts to address each of these issues individually, a principled framework that reconciles these two objectives has been missing in the CP literature. In this paper, we develop Conformal Prediction with Length-Optimization (CPL) - a novel and practical framework that constructs prediction sets with (near-) optimal length while ensuring conditional validity under various classes of covariate shifts, including the key cases of marginal and group-conditional coverage. In the infinite sample regime, we provide strong duality results which indicate that CPL achieves conditional validity and length optimality. In the finite sample regime, we show that CPL constructs conditionally valid prediction sets. Our extensive empirical evaluations demonstrate the superior prediction set size performance of CPL compared to state-of-the-art methods across diverse real-world and synthetic datasets in classification, regression, and large language model-based multiple choice question answering. An Implementation of our algorithm can be accessed at the following link: https://github.com/shayankiyani98/CP.

The neural moving horizon estimator (NMHE) is a relatively new and powerful state estimator that combines the strengths of neural networks (NNs) and model-based state estimation techniques. Various approaches exist for constructing NMHEs, each with its unique advantages and limitations. However, a comprehensive literature review that consolidates existing knowledge, outlines design guidelines and highlights future research directions is currently lacking. This systematic literature review synthesizes the existing knowledge on NMHE, addressing the above knowledge gap. The paper (1) explains the fundamental principles of NMHE, (2) explores different NMHE architectures, discussing the pros and cons of each, (3) investigates the NN architectures used in NMHE, providing insights for future designs, (4) examines the real-time implementability of current approaches, offering recommendations for practical applications, and (5) discusses the current limitations of NMHE approaches and outlines directions for future research. These insights can significantly improve the design and application of NMHE, which is critical for enhancing state estimation in complex systems.

This paper introduces a new multi-model predictive control (MMPC) method for quadrotor attitude control with performance nearly on par with nonlinear model predictive control (NMPC) and computational efficiency similar to linear model predictive control (LMPC). Conventional NMPC, while effective, is computationally intensive, especially for attitude control that needs a high refresh rate. Conversely, LMPC offers computational advantages but suffers from poor performance and local stability. Our approach relies on multiple linear models of attitude dynamics, each accompanied by a linear model predictive controller, dynamically switching between them given flight conditions. We leverage gap metric analysis to minimize the number of models required to accurately predict the vehicle behavior in various conditions and incorporate a soft switching mechanism to ensure system stability during controller transitions. Our results show that with just 15 models, the vehicle attitude can be accurately controlled across various set points. Comparative evaluations with existing controllers such as incremental nonlinear dynamic inversion, sliding mode control, LMPC, and NMPC reveal that our approach closely matches the effectiveness of NMPC, outperforming other methods, with a running time comparable to LMPC.

Cryo-EM is an increasingly popular method for determining the atomic resolution 3D structure of macromolecular complexes (eg, proteins) from noisy 2D images captured by an electron microscope. The computational task is to reconstruct the 3D density of the particle, along with 3D pose of the particle in each 2D image, for which the posterior pose distribution is highly multi-modal. Recent developments in cryo-EM have focused on deep learning for which amortized inference has been used to predict pose. Here, we address key problems with this approach, and propose a new semi-amortized method, cryoSPIN, in which reconstruction begins with amortized inference and then switches to a form of auto-decoding to refine poses locally using stochastic gradient descent. Through evaluation on synthetic datasets, we demonstrate that cryoSPIN is able to handle multi-modal pose distributions during the amortized inference stage, while the later, more flexible stage of direct pose optimization yields faster and more accurate convergence of poses compared to baselines. On experimental data, we show that cryoSPIN outperforms the state-of-the-art cryoAI in speed and reconstruction quality., Comment: NeurIPS 2024, Project webpage: https://shekshaa.github.io/semi-amortized-cryoem

Cyber-Physical Systems (CPS) consist of software interacting with the physical world, such as robots, vehicles, and industrial processes. CPS are frequently responsible for the safety of lives, property, or the environment, and so software correctness must be determined with a high degree of certainty. To that end, simply testing a CPS is insufficient, as its interactions with the physical world may be difficult to predict, and unsafe conditions may not be immediately obvious. Formal verification can provide stronger safety guarantees but relies on the accuracy of the verified system in representing the real system. Bringing together verification and implementation can be challenging, as languages that are typically used to implement CPS are not easy to formally verify, and languages that lend themselves well to verification often abstract away low-level implementation details. Translation between verification and implementation languages is possible, but requires additional assurances in the translation process and increases software complexity; having both in a single language is desirable. This paper presents a formalization of MARVeLus, a CPS language which combines verification and implementation. We develop a metatheory for its synchronous refinement type system and demonstrate verified synchronous programs executing on real systems.

This paper presents a new flight control framework for tilt-rotor multirotor uncrewed aerial vehicles (MRUAVs). Tiltrotor designs offer full actuation but introduce complexity in control allocation due to actuator redundancy. We propose a new approach where the allocator is tightly coupled with the controller, ensuring that the control signals generated by the controller are feasible within the vehicle actuation space. We leverage nonlinear model predictive control (NMPC) to implement the above framework, providing feasible control signals and optimizing performance. This unified control structure simultaneously manages both position and attitude, which eliminates the need for cascaded position and attitude control loops. Extensive numerical experiments demonstrate that our approach significantly outperforms conventional techniques that are based on linear quadratic regulator (LQR) and sliding mode control (SMC), especially in high-acceleration trajectories and disturbance rejection scenarios, making the proposed approach a viable option for enhanced control precision and robustness, particularly in challenging missions.

An integrated sensing and backscatter communication (ISABC) system is introduced herein. This system features a full-duplex (FD) base station (BS) that seamlessly merges sensing with backscatter communication and supports multiple users. Multiple access (MA) for the user is provided by employing rate-splitting multiple access (RSMA). RSMA, unlike other classical orthogonal and non-orthogonal MA schemes, splits messages into common and private streams. With RSMA, the set of common rate forms can be optimized to reduce interference. Optimized formulas are thus derived for communication rates for users, tags, and the BS's sensing rate, with the primary goal of enhancing the transmission efficiency of the BS. The optimization task involves minimizing the BS's overall transmission power by jointly optimizing the BS's beamforming vectors, the tag reflection coefficients, and user common rates. The alternating optimization method is employed to address this challenge. Concrete solutions are provided for the received beamformers, and semi-definite relaxation and slack-optimization techniques are adopted for transmit beamformers and reflection coefficients, respectively. For example, the proposed RSMA-assisted ISABC system achieves a 350% communication rate boost over a nonorthogonal multiple access-assisted ISABC, with only a 24% increase in transmit power, leveraging ten transmit/reception antennas at the BS., Comment: 13 pages, 8 figures, Journal paper

Students often enter physics classrooms with deeply ingrained misconceptions stemming from everyday experiences. These misconceptions challenge educators, as students often resist information that conflicts with their preconceptions. The first aim of this manuscript is to summarize the existing literature on misconceptions in university physics, reviewing misconceptions' sources, diagnoses, and remediation strategies. Most of this literature has concentrated on classical physics. However, quantum physics poses unique challenges because its concepts are removed from everyday experiences. This signals the need to ask how well existing strategies for addressing misconceptions apply to quantum physics. This is underscored by the recent surge of people from diverse backgrounds entering quantum physics because of the growing significance of quantum technologies. To help answer this question, we conducted in-depth interviews with quantum physics instructors at the University of Waterloo who have collectively taught over 100 quantum physics courses. These interviews explored common misconceptions in quantum physics, their origins, and effective instructional techniques to address them. We highlight specific misconceptions, such as misunderstanding of entanglement and spin, and successful teaching strategies, including ``misconception-trap quizzes.'' We integrate insights from the literature review with our interview data to provide an overview of current best practices in addressing physics misconceptions. Furthermore, we identify key research questions that warrant further exploration, such as the efficacy of multi-tier tests in quantum physics and developing a cohesive quantum curriculum. This paper aims to inform educators and curriculum developers, offering practical recommendations and setting a research agenda to improve conceptual understanding in classical and quantum physics., Comment: 10 pages, 0 figures

In this work, a deep learning-based technique is used to study the image-to-joint inverse kinematics of a tendon-driven supportive continuum arm. An eye-off-hand configuration is considered by mounting a camera at a fixed pose with respect to the inertial frame attached at the arm base. This camera captures an image for each distinct joint variable at each sampling time to construct the training dataset. This dataset is then employed to adapt a feed-forward deep convolutional neural network, namely the modified VGG-16 model, to estimate the joint variable. One thousand images are recorded to train the deep network, and transfer learning and fine-tuning techniques are applied to the modified VGG-16 to further improve the training. Finally, training is also completed with a larger dataset of images that are affected by various types of noises, changes in illumination, and partial occlusion. The main contribution of this research is the development of an image-to-joint network that can estimate the joint variable given an image of the arm, even if the image is not captured in an ideal condition. The key benefits of this research are twofold: 1) image-to-joint mapping can offer a real-time alternative to computationally complex inverse kinematic mapping through analytical models; and 2) the proposed technique can provide robustness against noise, occlusion, and changes in illumination. The dataset is publicly available on Kaggle., Comment: Presented at the Candian Conference on Robots and Vision (CRV)

Translating natural language questions into SQL queries, known as text-to-SQL, is a long-standing research problem. Effective text-to-SQL synthesis can become very challenging due to (i) the extensive size of database catalogs (descriptions of tables and their columns) and database values, (ii) reasoning over large database schemas, (iii) ensuring the functional validity of the generated queries, and (iv) navigating the ambiguities of natural language questions. We introduce CHESS, a Large Language Model (LLM) based multi-agent framework for efficient and scalable SQL synthesis, comprising four specialized agents, each targeting one of the aforementioned challenges: the Information Retriever (IR) extracts relevant data, the Schema Selector (SS) prunes large schemas, the Candidate Generator (CG) generates high-quality candidates and refines queries iteratively, and the Unit Tester (UT) validates queries through LLM-based natural language unit tests. Our framework offers configurable features that adapt to various deployment constraints, including 1) Supporting industrial-scale databases: leveraging the Schema Selector agent, CHESS efficiently narrows down very large database schemas into manageable sub-schemas, boosting system accuracy by approximately $2\%$ and reducing the number of LLM tokens by $\times 5$. 2) State-of-the-Art privacy-preserving performance: Among the methods using open-source models, CHESS achieves state-of-the-art performance, resulting in a high-performing, privacy-preserving system suitable for industrial deployment. 3) Scalablity with additional compute budget: In settings with high computational budgets, CHESS achieves $71.10\%$ accuracy on the BIRD test set, within $2\%$ of the leading proprietary method, while requiring approximately $83\%$ fewer LLM calls.

Transversal gates are logical gate operations on encoded quantum information that are efficient in gate count and depth, and are designed to minimize error propagation. Efficient encoding circuits for quantum codes that admit transversal gates are thus crucial to reduce noise and realize useful quantum computers. The class of punctured Quantum Reed-Muller codes admit transversal gates. We construct resource efficient recursive encoders for the class of quantum codes constructed from Reed-Muller and punctured Reed-Muller codes. These encoders on $n$ qubits have circuit depth of $O(\log n)$ and lower gate counts compared to previous works. The number of CNOT gates in the encoder across bi-partitions of the qubits is found to be equal to the entanglement entropy across these partitions, demonstrating that the encoder is optimal in terms of CNOT gates across these partitions. Finally, connecting these ideas, we explicitly show that entanglement can be extracted from QRM codewords., Comment: 33 pages

Adversarial training (AT) is a popular method for training robust deep neural networks (DNNs) against adversarial attacks. Yet, AT suffers from two shortcomings: (i) the robustness of DNNs trained by AT is highly intertwined with the size of the DNNs, posing challenges in achieving robustness in smaller models; and (ii) the adversarial samples employed during the AT process exhibit poor generalization, leaving DNNs vulnerable to unforeseen attack types. To address these dual challenges, this paper introduces adversarial training via adaptive knowledge amalgamation of an ensemble of teachers (AT-AKA). In particular, we generate a diverse set of adversarial samples as the inputs to an ensemble of teachers; and then, we adaptively amalgamate the logtis of these teachers to train a generalized-robust student. Through comprehensive experiments, we illustrate the superior efficacy of AT-AKA over existing AT methods and adversarial robustness distillation techniques against cutting-edge attacks, including AutoAttack.

In contemporary society, the application of artificial intelligence for automatic food recognition offers substantial potential for nutrition tracking, reducing food waste, and enhancing productivity in food production and consumption scenarios. Modern technologies such as Computer Vision and Deep Learning are highly beneficial, enabling machines to learn automatically, thereby facilitating automatic visual recognition. Despite some research in this field, the challenge of achieving accurate automatic food recognition quickly remains a significant research gap. Some models have been developed and implemented, but maintaining high performance swiftly, with low computational cost and low access to expensive hardware accelerators, still needs further exploration and research. This study employs the pretrained MobileNetV2 model, which is efficient and fast, for food recognition on the public Food11 dataset, comprising 16643 images. It also utilizes various techniques such as dataset understanding, transfer learning, data augmentation, regularization, dynamic learning rate, hyperparameter tuning, and consideration of images in different sizes to enhance performance and robustness. These techniques aid in choosing appropriate metrics, achieving better performance, avoiding overfitting and accuracy fluctuations, speeding up the model, and increasing the generalization of findings, making the study and its results applicable to practical applications. Despite employing a light model with a simpler structure and fewer trainable parameters compared to some deep and dense models in the deep learning area, it achieved commendable accuracy in a short time. This underscores the potential for practical implementation, which is the main intention of this study.

In $d=2j+1$ dimensions, the Landau-Streater quantum channel is defined on the basis of spin $j$ representation of the $su(2)$ algebra. Only for $j=1$, this channel is equivalent to the Werner-Holevo channel and enjoys covariance properties with respect to the group $SU(3)$. We extend this class of channels to higher dimensions in a way which is based on the Lie algebra $so(d)$ and $su(d)$. As a result it retains its equivalence to the Werner-Holevo channel in arbitrary dimensions. The resulting channel is covariant with respect to the unitary group $SU(d)$. We then modify this channel in a way which can act as a noisy channel on qudits. The resulting modified channel now interpolates between the identity channel and the Werner-Holevo channel and its covariance is reduced to the subgroup of orthogonal matrices $SO(d)$. We then investigate some of the propeties of the resulting two-parameter family of channels, including their spectrum, their regions of lack of indivisibility, their Holevo quantity, entanglement-assisted capacity and the closed form of their complement channel and a possible lower bound for their quantum capacity.

We propose fault-tolerant encoders for quantum low-density parity check (LDPC) codes. By grouping qubits within a quantum code over contiguous blocks and applying preshared entanglement across these blocks, we show how transversal implementation can be realized. The proposed encoder reduces the error propagation while using multi-qubit gates and is applicable for both entanglement-unassisted and entanglement-assisted quantum LDPC codes.