Computer Science and Engineeringhttps://repository.iitgn.ac.in/handle/123456789/4272021-12-01T15:28:03Z2021-12-01T15:28:03ZOn fair division with binary valuations respecting social networksMisra, NeeldharaNayak, Debanujhttps://repository.iitgn.ac.in/handle/123456789/73222021-12-01T13:18:12Z2021-11-01T00:00:00ZOn fair division with binary valuations respecting social networks
Misra, Neeldhara; Nayak, Debanuj
We study the computational complexity of finding fair allocations of indivisible goods in the setting where a social network on the agents is given. Notions of fairness in this context are "localized", that is, agents are only concerned about the bundles allocated to their neighbors, rather than every other agent in the system. We comprehensively address the computational complexity of finding locally envy-free and Pareto efficient allocations in the setting where the agents have binary valuations for the goods and the underlying social network is modeled by an undirected graph. We study the problem in the framework of parameterized complexity. We show that the problem is computationally intractable even in fairly restricted scenarios, for instance, even when the underlying graph is a path. We show NP-hardness for settings where the graph has only two distinct valuations among the agents. We demonstrate W-hardness with respect to the number of goods or the size of the vertex cover of the underlying graph. We also consider notions of proportionality that respect the structure of the underlying graph and show that two natural versions of this notion have different complexities: allocating according to the notion that accounts for locality to the greatest degree turns out to be computationally intractable, while for other notions, the allocation problem can be modeled as a structured ILP which can be solved efficiently
2021-11-01T00:00:00ZA tutorial-style introduction to DY*Bhargavan, KarthikeyanBichhawat, AbhishekHuy Do, QuocHosseyni, PedramK�sters, RalfSchmitz, GuidoW�rtele, Timhttps://repository.iitgn.ac.in/handle/123456789/73232021-12-01T13:18:12Z2021-12-01T00:00:00ZA tutorial-style introduction to DY*
Bhargavan, Karthikeyan; Bichhawat, Abhishek; Huy Do, Quoc; Hosseyni, Pedram; K�sters, Ralf; Schmitz, Guido; W�rtele, Tim
2021-12-01T00:00:00ZPrimitives enhancing GPU runtime support for improved DNN performanceDhakal, AdityaKulkarni, Sameer G.Ramakrishnan, K. K.https://repository.iitgn.ac.in/handle/123456789/73242021-12-01T13:18:12Z0005-08-21T00:00:00ZPrimitives enhancing GPU runtime support for improved DNN performance
Dhakal, Aditya; Kulkarni, Sameer G.; Ramakrishnan, K. K.
0005-08-21T00:00:00ZAn in-depth symbolic security analysis of the ACME standardBhargavan, KarthikeyanBichhawat, AbhishekHuy Do, QuocHosseyni, PedramKusters, RalfSchmitz, GuidoWurtele, Timhttps://repository.iitgn.ac.in/handle/123456789/72902021-11-24T13:31:14Z0015-11-21T00:00:00ZAn in-depth symbolic security analysis of the ACME standard
Bhargavan, Karthikeyan; Bichhawat, Abhishek; Huy Do, Quoc; Hosseyni, Pedram; Kusters, Ralf; Schmitz, Guido; Wurtele, Tim
0015-11-21T00:00:00Z