11 citations · 29 across the 22 of their papers we have counts for
3 papers · 1 filter
The Head Complexity of Boolean Functions in Single-Layer Attention
Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye
What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only mode…
One-way Communication Complexity of Minimum Vertex Cover in General Graphs
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman
We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the \(k\)-party one-way communication model. Edges of an arbitrary \(n\)-ve…
Reducibility Among Fractional Stability Problems
Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman +2
In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complet…