7 citations · 17 across the 12 of their papers we have counts for
13 papers
Collision Resistance of Single-Layer Neural Nets
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix , an…
Are Neural Networks Collision Resistant?
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity…
Overlap Gap and Computational Thresholds in the Square Wave Perceptron
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional li…
Optimal MEV Extraction Using Absolute Commitments
Daji Landis, Nikolaj I. Schwartzbach
We propose a new, more potent attack on decentralized exchanges. This attack leverages absolute commitments, which are commitments that can condition on the strategies made by othe…
Stackelberg Attacks on Auctions and Blockchain Transaction Fee Mechanisms
Daji Landis, Nikolaj I. Schwartzbach
We study an auction with identical items in a context where agents can arbitrarily commit to strategies. In general, such commitments non-trivially change the equilibria by…
Which Games are Unaffected by Absolute Commitments?
Daji Landis, Nikolaj I. Schwartzbach
We identify a subtle security issue that impacts mechanism design in scenarios in which agents can absolutely commit to strategies. Absolute commitments allow the strategy of an ag…
-SUM in the Sparse Regime
Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach +2
In the average-case -SUM problem, given integers chosen uniformly at random from , the objective is to find a ``solution'' set of numbers that sum to $0…
Side Contract Commitment Attacks on Blockchains
Daji Landis, Nikolaj I. Schwartzbach
We identify a subtle security issue that impacts the design of smart contracts, because agents may themselves deploy smart contracts (side contracts). Typically, equilibria of game…
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…
Outsourcing Adjudication to Strategic Jurors
Ioannis Caragiannis, Nikolaj I. Schwartzbach
We study a scenario where an adjudication task (e.g., the resolution of a binary dispute) is outsourced to a set of agents who are appointed as jurors. This scenario is particularl…
Game theory on the blockchain: a model for games with smart contracts
Mathias Hall-Andersen, Nikolaj I. Schwartzbach
We propose a model for games in which the players have shared access to a blockchain that allows them to deploy smart contracts to act on their behalf. This changes fundamental gam…
Payment Schemes from Limited Information with Applications in Distributed Computing
Nikolaj I. Schwartzbach
We propose a generic mechanism for incentivizing behavior in an arbitrary finite game using payments. Doing so is trivial if the mechanism is allowed to observe all actions taken i…
An Incentive-Compatible Smart Contract for Decentralized Commerce
Nikolaj Ignatieff Schwartzbach
We propose a smart contract that allows two mutually distrusting parties to transact any non-digital good or service by deploying a smart contract on a blockchain to act as escrow.…