4 papers
Tight Sample Bounds for Renyi and Min-Entropy Estimation
Arman Adibi, Piotr Krysta
Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive ac…
Selling Privacy in Blockchain Transactions
Georgios Chionas, Olga Gorelkina, Piotr Krysta +1
We study methods to enhance statistical privacy in blockchain transactions. We analyze economic mechanisms for privacy-aware transaction owners whose utility depends not only on th…
Position Auctions with a Capacity Constraint
Eleni Batziou, Georgios Birmpas, Georgios Chionas +1
Sponsored search auctions are commonly modeled as an assignment of a fixed set of slots (positions) to a set of advertisers, with welfare maximization being reducible to a standard…
Beating Competitive Ratio 4 for Graphic Matroid Secretary
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +3
One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered…