-
Post-Quantum Cryptography from Quantum Stabilizer Decoding
Authors:
Jonathan Z. Lu,
Alexander Poremba,
Yihui Quek,
Akshar Ramkumar
Abstract:
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied…
▽ More
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied LPN problem -- is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practical: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE, and our OT is round-optimal. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suit of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.
△ Less
Submitted 19 March, 2026;
originally announced March 2026.
-
Sparks of Cooperative Reasoning: LLMs as Strategic Hanabi Agents
Authors:
Mahesh Ramesh,
Kaousheik Jayakumar,
Aswinkumar Ramkumar,
Pavan Thodima,
Aniket Rege,
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Abstract:
Cooperative reasoning under incomplete information remains challenging for both humans and multi-agent systems. The card game Hanabi embodies this challenge, requiring theory-of-mind reasoning and strategic communication. We benchmark 17 state-of-the-art LLM agents in 2-5 player games and study the impact of context engineering across model scales (4B to 600B+) to understand persistent coordinatio…
▽ More
Cooperative reasoning under incomplete information remains challenging for both humans and multi-agent systems. The card game Hanabi embodies this challenge, requiring theory-of-mind reasoning and strategic communication. We benchmark 17 state-of-the-art LLM agents in 2-5 player games and study the impact of context engineering across model scales (4B to 600B+) to understand persistent coordination failures and robustness to scaffolding: from a minimal prompt with only explicit card details (Watson setting), to scaffolding with programmatic, Bayesian-motivated deductions (Sherlock setting), to multi-turn state tracking via working memory (Mycroft setting). We show that (1) agents can maintain an internal working memory for state tracking and (2) cross-play performance between different LLMs smoothly interpolates with model strength. In the Sherlock setting, the strongest reasoning models exceed 15 points on average across player counts, yet still trail experienced humans and specialist Hanabi agents, both consistently scoring above 20. We release the first public Hanabi datasets with annotated trajectories and move utilities: (1) HanabiLogs, containing 1,520 full game logs for instruction tuning, and (2) HanabiRewards, containing 560 games with dense move-level value annotations for all candidate moves. Supervised and RL finetuning of a 4B open-weight model (Qwen3-Instruct) on our datasets improves cooperative Hanabi play by 21% and 156% respectively, bringing performance to within ~3 points of a strong proprietary reasoning model (o4-mini) and surpassing the best non-reasoning model (GPT-4.1) by 52%. The HanabiRewards RL-finetuned model further generalizes beyond Hanabi, improving performance on a cooperative group-guessing benchmark by 11%, temporal reasoning on EventQA by 6.4%, instruction-following on IFBench-800K by 1.7 Pass@10, and matching AIME 2025 mathematical reasoning Pass@10.
△ Less
Submitted 16 March, 2026; v1 submitted 25 January, 2026;
originally announced January 2026.
-
Average-Case Complexity of Quantum Stabilizer Decoding
Authors:
Andrey Boris Khesin,
Jonathan Z. Lu,
Alexander Poremba,
Akshar Ramkumar,
Vinod Vaikuntanathan
Abstract:
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our und…
▽ More
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate--the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography.
More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding--all of which are classically identical--to have distinct or non-trivially equivalent complexity.
△ Less
Submitted 24 September, 2025;
originally announced September 2025.
-
High-Temperature Fermionic Gibbs States are Mixtures of Gaussian States
Authors:
Akshar Ramkumar,
Yiyi Cai,
Yu Tong,
Jiaqing Jiang
Abstract:
Efficient simulation of a quantum system generally relies on structural properties of the quantum state. Motivated by the recent results by Bakshi et al. on the sudden death of entanglement in high-temperature Gibbs states of quantum spin systems, we study the high-temperature Gibbs states of bounded-degree local fermionic Hamiltonians, which include the special case of geometrically local fermion…
▽ More
Efficient simulation of a quantum system generally relies on structural properties of the quantum state. Motivated by the recent results by Bakshi et al. on the sudden death of entanglement in high-temperature Gibbs states of quantum spin systems, we study the high-temperature Gibbs states of bounded-degree local fermionic Hamiltonians, which include the special case of geometrically local fermionic systems. We prove that at a sufficiently high temperature that is independent of the system size, the Gibbs state is a probabilistic mixture of fermionic Gaussian states. This forms the basis of an efficient classical algorithm to prepare the Gibbs state by sampling from a distribution of fermionic Gaussian states. As a contrasting example, we show that high-temperature Gibbs states of the Sachdev-Ye-Kitaev (SYK) model are not convex mixtures of Gaussian states.
△ Less
Submitted 17 January, 2026; v1 submitted 14 May, 2025;
originally announced May 2025.
-
Mixing time of quantum Gibbs sampling for random sparse Hamiltonians
Authors:
Akshar Ramkumar,
Mehdi Soleimanifar
Abstract:
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm by Chen, Kastoryano, and Gilyén provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The…
▽ More
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm by Chen, Kastoryano, and Gilyén provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n by n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.
△ Less
Submitted 7 November, 2024;
originally announced November 2024.
-
Towards a Multidimensional Evaluation Framework for Empathetic Conversational Systems
Authors:
Aravind Sesagiri Raamkumar,
Siyuan Brandon Loh
Abstract:
Empathetic Conversational Systems (ECS) are built to respond empathetically to the user's emotions and sentiments, regardless of the application domain. Current ECS studies evaluation approaches are restricted to offline evaluation experiments primarily for gold standard comparison & benchmarking, and user evaluation studies for collecting human ratings on specific constructs. These methods are in…
▽ More
Empathetic Conversational Systems (ECS) are built to respond empathetically to the user's emotions and sentiments, regardless of the application domain. Current ECS studies evaluation approaches are restricted to offline evaluation experiments primarily for gold standard comparison & benchmarking, and user evaluation studies for collecting human ratings on specific constructs. These methods are inadequate in measuring the actual quality of empathy in conversations. In this paper, we propose a multidimensional empathy evaluation framework with three new methods for measuring empathy at (i) structural level using three empathy-related dimensions, (ii) behavioral level using empathy behavioral types, and (iii) overall level using an empathy lexicon, thereby fortifying the evaluation process. Experiments were conducted with the state-of-the-art ECS models and large language models (LLMs) to show the framework's usefulness.
△ Less
Submitted 26 July, 2024;
originally announced July 2024.
-
MABViT -- Modified Attention Block Enhances Vision Transformers
Authors:
Mahesh Ramesh,
Aswinkumar Ramkumar
Abstract:
Recent studies have demonstrated the effectiveness of Gated Linear Units (GLU) in enhancing transformer models, particularly in Large Language Models (LLMs). Additionally, utilizing a parallel configuration within each Transformer block rather than the conventional serialized method has been revealed to accelerate the training of LLMs without significantly impacting performance. However, when the…
▽ More
Recent studies have demonstrated the effectiveness of Gated Linear Units (GLU) in enhancing transformer models, particularly in Large Language Models (LLMs). Additionally, utilizing a parallel configuration within each Transformer block rather than the conventional serialized method has been revealed to accelerate the training of LLMs without significantly impacting performance. However, when the MLP and attention block were run in parallel for the image classification task, we observed a noticeable decline in performance. We propose a novel transformer variant that integrates non-linearity within the attention block to tackle this problem. We implemented the GLU-based activation function on the Value tensor, and this new technique surpasses the current state-of-the-art S/16 variant of Vision Transformers by 0.6% on the ImageNet-1K dataset while utilizing fewer parameters. It also supersedes the B/16 variant while using only half the parameters. Furthermore, we provide results with the GELU activation function variant to confirm our assertions. Lastly, we showcase that the MABViT variants exhibit greater potential when utilized in deep transformers compared to the standard architecture.
△ Less
Submitted 1 January, 2024; v1 submitted 3 December, 2023;
originally announced December 2023.
-
Harnessing Large Language Models' Empathetic Response Generation Capabilities for Online Mental Health Counselling Support
Authors:
Siyuan Brandon Loh,
Aravind Sesagiri Raamkumar
Abstract:
Large Language Models (LLMs) have demonstrated remarkable performance across various information-seeking and reasoning tasks. These computational systems drive state-of-the-art dialogue systems, such as ChatGPT and Bard. They also carry substantial promise in meeting the growing demands of mental health care, albeit relatively unexplored. As such, this study sought to examine LLMs' capability to g…
▽ More
Large Language Models (LLMs) have demonstrated remarkable performance across various information-seeking and reasoning tasks. These computational systems drive state-of-the-art dialogue systems, such as ChatGPT and Bard. They also carry substantial promise in meeting the growing demands of mental health care, albeit relatively unexplored. As such, this study sought to examine LLMs' capability to generate empathetic responses in conversations that emulate those in a mental health counselling setting. We selected five LLMs: version 3.5 and version 4 of the Generative Pre-training (GPT), Vicuna FastChat-T5, Pathways Language Model (PaLM) version 2, and Falcon-7B-Instruct. Based on a simple instructional prompt, these models responded to utterances derived from the EmpatheticDialogues (ED) dataset. Using three empathy-related metrics, we compared their responses to those from traditional response generation dialogue systems, which were fine-tuned on the ED dataset, along with human-generated responses. Notably, we discovered that responses from the LLMs were remarkably more empathetic in most scenarios. We position our findings in light of catapulting advancements in creating empathetic conversational systems.
△ Less
Submitted 11 October, 2023;
originally announced October 2023.
-
Empathetic Conversational Systems: A Review of Current Advances, Gaps, and Opportunities
Authors:
Aravind Sesagiri Raamkumar,
Yinping Yang
Abstract:
Empathy is a vital factor that contributes to mutual understanding, and joint problem-solving. In recent years, a growing number of studies have recognized the benefits of empathy and started to incorporate empathy in conversational systems. We refer to this topic as empathetic conversational systems. To identify the critical gaps and future opportunities in this topic, this paper examines this ra…
▽ More
Empathy is a vital factor that contributes to mutual understanding, and joint problem-solving. In recent years, a growing number of studies have recognized the benefits of empathy and started to incorporate empathy in conversational systems. We refer to this topic as empathetic conversational systems. To identify the critical gaps and future opportunities in this topic, this paper examines this rapidly growing field using five review dimensions: (i) conceptual empathy models and frameworks, (ii) adopted empathy-related concepts, (iii) datasets and algorithmic techniques developed, (iv) evaluation strategies, and (v) state-of-the-art approaches. The findings show that most studies have centered on the use of the EMPATHETICDIALOGUES dataset, and the text-based modality dominates research in this field. Studies mainly focused on extracting features from the messages of the users and the conversational systems, with minimal emphasis on user modeling and profiling. Notably, studies that have incorporated emotion causes, external knowledge, and affect matching in the response generation models, have obtained significantly better results. For implementation in diverse real-world settings, we recommend that future studies should address key gaps in areas of detecting and authenticating emotions at the entity level, handling multimodal inputs, displaying more nuanced empathetic behaviors, and encompassing additional dialogue system features.
△ Less
Submitted 8 November, 2022; v1 submitted 9 May, 2022;
originally announced June 2022.
-
Mathematical Properties of Generalized Shape Expansion-Based Motion Planning Algorithms
Authors:
Adhvaith Ramkumar,
Vrushabh Zinage,
Satadal Ghosh
Abstract:
Motion planning is an essential aspect of autonomous systems and robotics and is an active area of research. A recently-proposed sampling-based motion planning algorithm, termed 'Generalized Shape Expansion' (GSE), has been shown to possess significant improvement in computational time over several existing well-established algorithms. The GSE has also been shown to be probabilistically complete.…
▽ More
Motion planning is an essential aspect of autonomous systems and robotics and is an active area of research. A recently-proposed sampling-based motion planning algorithm, termed 'Generalized Shape Expansion' (GSE), has been shown to possess significant improvement in computational time over several existing well-established algorithms. The GSE has also been shown to be probabilistically complete. However, asymptotic optimality of the GSE is yet to be studied. To this end, in this paper we show that the GSE algorithm is not asymptotically optimal by studying its behaviour for the promenade problem. In order to obtain a probabilistically complete and asymptotically optimal generalized shape-based algorithm, a modified version of the GSE, namely 'GSE*' algorithm, is subsequently presented. The forementioned desired mathematical properties of the GSE* algorithm are justified by its detailed analysis. Numerical simulations are found to be in line with the theoretical results on the GSE* algorithm.
△ Less
Submitted 22 February, 2021;
originally announced February 2021.
-
Understanding the Twitter Usage of Science Citation Index (SCI) Journals
Authors:
Aravind Sesagiri Raamkumar,
Mojisola Erdt,
Harsha Vijayakumar,
Aarthy Nagarajan,
Yin-Leng Theng
Abstract:
This paper investigates the Twitter interaction patterns of journals from the Science Citation Index (SCI) of Master Journal List (MJL). A total of 953,253 tweets extracted from 857 journal accounts, were analyzed in this study. Findings indicate that SCI journals interacted more with each other but much less with journals from other citation indices. The network structure of the communication gra…
▽ More
This paper investigates the Twitter interaction patterns of journals from the Science Citation Index (SCI) of Master Journal List (MJL). A total of 953,253 tweets extracted from 857 journal accounts, were analyzed in this study. Findings indicate that SCI journals interacted more with each other but much less with journals from other citation indices. The network structure of the communication graph resembled a tight crowd network, with Nature journals playing a major part. Information sources such as news portals and scientific organizations were mentioned more in tweets, than academic journal Twitter accounts. Journals with high journal impact factors (JIFs) were found to be prominent hubs in the communication graph. Differences were found between the Twitter usage of SCI journals with Humanities and Social Sciences (HSS) journals.
△ Less
Submitted 25 September, 2019;
originally announced September 2019.
-
Understanding the Twitter Usage of Humanities and Social Sciences Academic Journals
Authors:
Aravind Sesagiri Raamkumar,
Mojisola Erdt,
Harsha Vijayakumar,
Edie Rasmussen,
Yin-Leng Theng
Abstract:
Scholarly communication has the scope to transcend the limitations of the physical world through social media extended coverage and shortened information paths. Accordingly, publishers have created profiles for their journals in Twitter to promote their publications and to initiate discussions with public. This paper investigates the Twitter presence of humanities and social sciences (HSS) journal…
▽ More
Scholarly communication has the scope to transcend the limitations of the physical world through social media extended coverage and shortened information paths. Accordingly, publishers have created profiles for their journals in Twitter to promote their publications and to initiate discussions with public. This paper investigates the Twitter presence of humanities and social sciences (HSS) journal titles obtained from mainstream citation indices, by analysing the interaction and communication patterns. This study utilizes webometric data collection, descriptive analysis, and social network analysis. Findings indicate that the presence of HSS journals in Twitter across disciplines is not yet substantial. Sharing of general websites appears to be the key activity performed by HSS journals in Twitter. Among them, web content from news portals and magazines are highly disseminated. Sharing of research articles and retweeting was not majorly observed. Inter-journal communication is apparent within the same citation index, but it is very minimal with journals from the other index. However, there seems to be an effort to broaden communication beyond the research community, reaching out to connect with the public.
△ Less
Submitted 15 July, 2018;
originally announced July 2018.
-
A Framework for Scientific Paper Retrieval and Recommender Systems
Authors:
Aravind Sesagiri Raamkumar,
Schubert Foo,
Natalie Pang
Abstract:
Information retrieval (IR) and recommender systems (RS) have been employed for addressing search tasks executed during literature review and the overall scholarly communication lifecycle. Majority of the studies have concentrated on algorithm design for improving the accuracy and usefulness of these systems. Contextual elements related to the scholarly tasks have been largely ignored. In this pape…
▽ More
Information retrieval (IR) and recommender systems (RS) have been employed for addressing search tasks executed during literature review and the overall scholarly communication lifecycle. Majority of the studies have concentrated on algorithm design for improving the accuracy and usefulness of these systems. Contextual elements related to the scholarly tasks have been largely ignored. In this paper, we propose a framework called the Scientific Paper Recommender and Retrieval Framework (SPRRF) that combines aspects of user role modeling and user-interface features with IR/RS components. The framework is based on eight emergent themes identified from participants feedback in a user evaluation study conducted with a prototype assistive system. 119 researchers participated in the study for evaluating the prototype system that provides recommendations for two literature review and one manuscript writing tasks. This holistic framework is meant to guide future studies in this area.
△ Less
Submitted 6 September, 2016;
originally announced September 2016.
-
Whats in a Country Name - Twitter Hashtag Analysis of #singapore
Authors:
Aravind Sesagiri Raamkumar
Abstract:
Twitter as a micro-blogging platform rose to instant fame mainly due to its minimalist features that allow seamless communication between users. As the conversations grew thick and faster, a placeholder feature called as Hashtags became important as it captured the themes behind the tweets. Prior studies have investigated the conversation dynamics, inter-play with other media platforms and communi…
▽ More
Twitter as a micro-blogging platform rose to instant fame mainly due to its minimalist features that allow seamless communication between users. As the conversations grew thick and faster, a placeholder feature called as Hashtags became important as it captured the themes behind the tweets. Prior studies have investigated the conversation dynamics, inter-play with other media platforms and communication patterns between users for specific event-based hashtags such as the #Occupy movement. Commonplace hashtags which are used on a daily basis have been largely ignored due to their seemingly innocuous presence in tweets and also due to the lack of connection with real-world events. However, it can be postulated that utility of these hashtags is the main reason behind their continued usage. This study is aimed at understanding the rationale behind the usage of a particular type of commonplace hashtags - location hashtags such as country and city name hashtags. Tweets with the hashtag #singapore were extracted for one week duration. Manual and automatic tweet classification was performed along with social network analysis, to identify the underlying themes. Seven themes were identified. Findings indicate that the hashtag is prominent in tweets about local events, local news, users current location and landmark related information sharing. Users who share content from social media sites such as Instagram make use of the hashtag in a more prominent way when compared to users who post textual content. News agencies, commercial bodies and celebrities make use of the hashtag more than common individuals. Overall, the results show the non-conversational nature of the hashtag. The findings are to be validated with other country names and cross-validated with hashtag data from other social media platforms.
△ Less
Submitted 16 January, 2016;
originally announced January 2016.
-
Designing a Linked Data Migrational Framework for Singapore Government Datasets
Authors:
Aravind Sesagiri Raamkumar,
Muthu Kumaar Thangavelu,
Sudarsan Kaleeswaran amd Christopher S. G. Khoo
Abstract:
The subject area of this report is Linked Data and its application to the Government domain. Linked Data is an alternative method of data representation that aims to interlink data from varied sources through relationships. Governments around the world have started publishing their data in this format to assist citizens in making better use of public services. This report provides an eight step mi…
▽ More
The subject area of this report is Linked Data and its application to the Government domain. Linked Data is an alternative method of data representation that aims to interlink data from varied sources through relationships. Governments around the world have started publishing their data in this format to assist citizens in making better use of public services. This report provides an eight step migrational framework for converting Singapore Government data from legacy systems to Linked Data format. The framework formulation is based on a study of the Singapore data ecosystem with help from Infocomm Development Authority (iDA) of Singapore. Each step in the migrational framework has been constructed with objectives, recommendations, best practices and issues with entry and exit points. This work builds on the existing Linked Data literature, implementations in other countries and cookbooks provided by Linked Data researchers. iDA can use this report to gain an understanding of the effort and work involved in the implementation of Linked Data system on top of their legacy systems. The framework can be evaluated by building a Proof of Concept (POC) application.
△ Less
Submitted 8 April, 2015;
originally announced April 2015.