"computational complexity" Papers
49 papers found
Conference
Additive Models Explained: A Computational Complexity Approach
Shahaf Bassan, Michal Moshkovitz, Guy Katz
Balanced and Fair Partitioning of Friends
Argyrios Deligkas, Eduard Eiben, Stavros D. Ioannidis et al.
Bounds on the computational complexity of neurons due to dendritic morphology
Anamika Agrawal, Michael Buice
CATANet: Efficient Content-Aware Token Aggregation for Lightweight Image Super-Resolution
Xin Liu, Jie Liu, Jie Tang et al.
Complexity Experts are Task-Discriminative Learners for Any Image Restoration
Eduard Zamfir, Zongwei Wu, Nancy Mehta et al.
Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability
Shayan Karimi, Xiaoqi Tan
Efficient Attention-Sharing Information Distillation Transformer for Lightweight Single Image Super-Resolution
Karam Park, Jae Woong Soh, Nam Ik Cho
Efficient Sparse PCA via Block-Diagonalization
Alberto Del Pia, Dekun Zhou, Yinglun Zhu
Fair and Efficient Completion of Indivisible Goods
Vishwa Prakash HV, Ayumi Igarashi, Rohit Vaish
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy
Julian Dörfler, Benito van der Zander, Markus Bläser et al.
Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency
Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani et al.
HSI: A Holistic Style Injector for Arbitrary Style Transfer
Shuhao Zhang, Hui Kang, Yang Liu et al.
Improving Energy Natural Gradient Descent through Woodbury, Momentum, and Randomization
Andrés Guzmán-Cordero, Felix Dangel, Gil Goldshlager et al.
Learning More Expressive General Policies for Classical Planning Domains
Simon Ståhlberg, Blai Bonet, Hector Geffner
Learning single index models via harmonic decomposition
Nirmit Joshi, Hugo Koubbi, Theodor Misiakiewicz et al.
Memory-Reduced Meta-Learning with Guaranteed Convergence
Honglin Yang, Ji Ma, Xiao Yu
OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
Antoine de Mathelin, Nicolas Enrique Cecchi, François Deheeger et al.
On the self-verification limitations of large language models on reasoning and planning tasks
Kaya Stechly, Karthik Valmeekam, Subbarao Kambhampati
Second-Order Min-Max Optimization with Lazy Hessians
Lesi Chen, Chengchang Liu, Jingzhao Zhang
Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors
Guangyi Zhang, Qiyu Liu, Aristides Gionis
SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
Reda Marzouk, Shahaf Bassan, Guy Katz
The Complexity of Extending Fair Allocations of Indivisible Goods
Argyrios Deligkas, Eduard Eiben, Robert Ganian et al.
The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm et al.
The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Moritz Stargalla, Christoph Hertrich, Daniel Reichman
The Cost Perspective of Liquid Democracy: Feasibility and Control
Shiri Alouf-Heffetz, Łukasz Janeczko, Grzegorz Lisowski et al.
VSSD: Vision Mamba with Non-Causal State Space Duality
Yuheng Shi, Mingjia Li, Minjing Dong et al.
ZeroS: Zero‑Sum Linear Attention for Efficient Transformers
Jiecheng Lu, Xu Han, Yan Sun et al.
A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagrams
Rolando Kindelan Nuñez, Mircea Petrache, Mauricio Cerda et al.
Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
Jan van den Brand, Zhao Song, Tianyi Zhou
Arrows of Time for Large Language Models
Vassilis Papadopoulos, Jérémie Wenger, Clement Hongler
Collaborative Learning with Different Labeling Functions
yuyang deng, Mingda Qiao
Cost Minimization for Equilibrium Transition
Haoqiang Huang, Zihe Wang, Zhide Wei et al.
Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization
Shaohan Li, Yunpeng Shi, Gilad Lerman
Envy-Free House Allocation under Uncertain Preferences
Haris Aziz, Isaiah Iliffe, Bo Li et al.
Faster Maximum Inner Product Search in High Dimensions
Mo Tiwari, Ryan Kang, Jaeyong Lee et al.
How to Make Knockout Tournaments More Popular?
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
Improving Computational Complexity in Statistical Models with Local Curvature Information
Pedram Akbarian, Tongzheng Ren, Jiacheng Zhuo et al.
Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics
Siqi Miao, Zhiyuan Lu, Mia Liu et al.
Mobile Attention: Mobile-Friendly Linear-Attention for Vision Transformers
Zhiyu Yao, Jian Wang, Haixu Wu et al.
Non-flat ABA Is an Instance of Bipolar Argumentation
Markus Ulbricht, Nico Potyka, Anna Rapberger et al.
On the Tractability of SHAP Explanations under Markovian Distributions
Reda Marzouk, De la Higuera
Reachability of Fair Allocations via Sequential Exchanges
Ayumi Igarashi, Naoyuki Kamiyama, Warut Suksompong et al.
Sparse Refinement for Efficient High-Resolution Semantic Segmentation
Zhijian Liu, Zhuoyang Zhang, Samir Khaki et al.
Spatial Voting with Incomplete Voter Information
Aviram Imber, Jonas Israel, Markus Brill et al.
Tensorial template matching for fast cross-correlation with rotations and its application for tomography
Antonio Martinez-Sanchez, Ulrike Homberg, J. M. Almira et al.
The Computational Complexity of Finding Second-Order Stationary Points
Andreas Kontogiannis, Vasilis Pollatos, Sotiris Kanellopoulos et al.
Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover
Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono et al.
Transformers, parallel computation, and logarithmic depth
Clayton Sanford, Daniel Hsu, Matus Telgarsky
Unravelling Expressive Delegations: Complexity and Normative Analysis
Giannis Tyrovolas, Andrei Constantinescu, Edith Elkind