Computational Complexity

New submissions

• New submissions
• Replacements

New submissions for Fri, 7 Jun 24

[1]  arXiv:2406.04046 [pdf, other]

Title: ActionReasoningBench: Reasoning about Actions with and without Ramification Constraints

Authors: Divij Handa, Pavel Dolin, Shrinidhi Kumbhar, Chitta Baral, Tran Cao Son

Comments: 54 pages, 11 figures

Subjects: Computational Complexity (cs.CC); Artificial Intelligence (cs.AI)

Reasoning about actions and change (RAC) has historically driven the development of many early AI challenges, such as the frame problem, and many AI disciplines, including non-monotonic and commonsense reasoning. The role of RAC remains important even now, particularly for tasks involving dynamic environments, interactive scenarios, and commonsense reasoning. Despite the progress of Large Language Models (LLMs) in various AI domains, their performance on RAC is underexplored. To address this gap, we introduce a new benchmark, ActionReasoningBench, encompassing 13 domains and rigorously evaluating LLMs across eight different areas of RAC. These include - Object Tracking, Fluent Tracking, State Tracking, Action Executability, Effects of Actions, Numerical RAC, Hallucination Detection, and Composite Questions. Furthermore, we also investigate the indirect effect of actions due to ramification constraints for every domain. Finally, we evaluate our benchmark using open-sourced and commercial state-of-the-art LLMs, including GPT-4o, Gemini-1.0-Pro, Llama2-7b-chat, Llama2-13b-chat, Llama3-8b-instruct, Gemma-2b-instruct, and Gemma-7b-instruct. Our findings indicate that these models face significant challenges across all categories included in our benchmark.

Replacements for Fri, 7 Jun 24

[2]  arXiv:2109.11725 (replaced) [pdf, other]

Title: Punctured Low-Bias Codes Behave Like Random Linear Codes

Authors: Venkatesan Guruswami, Jonathan Mosheiff

Subjects: Computational Complexity (cs.CC); Information Theory (cs.IT); Combinatorics (math.CO)

[3]  arXiv:2406.01057 (replaced) [pdf, other]

Title: Knapsack with Vertex Cover, Set Cover, and Hitting Set

Authors: Palash Dey, Ashlesha Hota, Sudeshna Kolay, Sipra Singh

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

• New submissions
• Replacements