Fetching the paper…
Reading the bibliography…
Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities" -- what is the probability of 5-year survival after cancer diagnosis? -- and which increasingly form the basis for life-altering decisions.
Objective probability forecasts’
AP Dawid · 1982
Earlier work this paper cites.
A theory of the learnable
Leslie G Valiant · 1984
Earlier work this paper cites.
A hard-core predicate for all one-way functions
Oded Goldreich and Leonid A Levin · 1989
Earlier work this paper cites.
New directions in testing
Richard J. Lipton · 1989
Earlier work this paper cites.
Pricing via processing or combatting junk mail
Cynthia Dwork and Moni Naor · 1992
Earlier work this paper cites.
Decision theoretic generalizations of the pac model for neural net and other learning applications
David Haussler · 1992
Earlier work this paper cites.
Efficient distribution-free learning of probabilistic concepts
Michael J Kearns and Robert E Schapire · 1994
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J Kearns, Robert E Schapire, and Linda M Sellie · 1994
Earlier work this paper cites.
The weighted majority algorithm
Nick Littlestone and Manfred K Warmuth · 1994
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Yoav Freund and Robert E Schapire · 1997
Earlier work this paper cites.
Asymptotic calibration
Dean P Foster and Rakesh V Vohra · 1998
Earlier work this paper cites.
Parameterized Complexity
Rodney G. Downey and Michael R. Fellows · 1999
Earlier work this paper cites.
An easier way to calibrate
Drew Fudenberg and David K Levine · 1999
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Pseudorandom generators without the XOR lemma
Madhu Sudan, Luca Trevisan, and Salil P. Vadhan · 2001
Earlier work this paper cites.
The reproducible properties of correct forecasts
Alvaro Sandroni · 2003
Earlier work this paper cites.
Calibration with many checking rules
Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra · 2003
Earlier work this paper cites.
The parameterized complexity of counting problems
Jörg Flum and Martin Grohe · 2004
Earlier work this paper cites.
Tight lower bounds for certain parameterized np-hard problems
Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia · 2005
Earlier work this paper cites.
Strong computational lower bounds via parameterized complexity
Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia · 2006
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Foundations of Cryptography: Volume 1, Basic Tools
Oded Goldreich · 2006
Earlier work this paper cites.
From external to internal regret
Avrim Blum and Yishay Mansour · 2007
Cited alongside, same era.
Pseudorandomness and average-case complexity via uniform reductions
Luca Trevisan and Salil P. Vadhan · 2007
Cited alongside, same era.
Computational Complexity: A Conceptual Perspective
Oded Goldreich · 2008
Cited alongside, same era.
On agnostic boosting and parity learning
Adam Tauman Kalai, Yishay Mansour, and Elad Verbin · 2008
Cited alongside, same era.
Foundations of Cryptography: Volume 2, Basic Applications
Oded Goldreich · 2009
Cited alongside, same era.
Regularity, boosting, and efficiently simulating every high-entropy distribution
Luca Trevisan, Madhur Tulsiani, and Salil Vadhan · 2009
Cited alongside, same era.
Inherent trade-offs in the fair determination of risk scores
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan · 2016
Later among the works it cites.
Average-case fine-grained hardness
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan · 2017
Later among the works it cites.
If the current clique algorithms are optimal, so is valiant’s parser
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams · 2018
Later among the works it cites.
Proofs of work from worst-case assumptions
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan · 2018
Later among the works it cites.
Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems
Oded Goldreich and Guy N. Rothblum · 2018
Later among the works it cites.
Multicalibration: Calibration for the (computationally-identifiable) masses
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Distribution-specific agnostic boosting
Vitaly Feldman · 2010
Cited alongside, same era.
The learning with errors problem
Oded Regev · 2010
Cited alongside, same era.
Fairness through awareness
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel · 2012
Cited alongside, same era.
Amplifying circuit lower bounds against polynomial time with applications
Richard J Lipton and Ryan Williams · 2012
Cited alongside, same era.
Pseudorandomness
Salil P. Vadhan · 2012
Cited alongside, same era.
Losing weight by gaining edges
Amir Abboud, Kevin Lewi, and Ryan Williams · 2014
Cited alongside, same era.
Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy Rothblum · 2018
Later among the works it cites.
Preventing fairness gerrymandering: Auditing and learning for subgroup fairness
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu · 2018
Later among the works it cites.
Fairness through computationally-bounded awareness
Michael P. Kim, Omer Reingold, and Guy N. Rothblum · 2018
Later among the works it cites.
Fine-grained reductions and quantum speedups for dynamic programming
Amir Abboud · 2019
Later among the works it cites.
Sample amplification: Increasing dataset size even when learning is impossible
Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant · 2019
Later among the works it cites.
The average-case complexity of counting cliques in erdos-rényi hypergraphs
Enric Boix-Adserà, Matthew Brennan, and Guy Bresler · 2019
Later among the works it cites.
Advancing subgroup fairness via sleeping experts
Avrim Blum and Thodoris Lykouris · 2019
Later among the works it cites.
Learning from outcomes: Evidence-based rankings
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona · 2019
Later among the works it cites.
Multiaccuracy: Black-box post-processing for fairness in classification
Michael P. Kim, Amirata Ghorbani, and James Zou · 2019
Later among the works it cites.
An empirical study of rich subgroup fairness for machine learning
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu · 2019
Later among the works it cites.
New techniques for proving fine-grained average-case hardness
Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams · 2020
Closest in time.
On counting $t$-cliques mod 2
Oded Goldreich · 2020
Closest in time.
Moment multicalibration for uncertainty estimation
Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra · 2020
Closest in time.
A Complexity-Theoretic Perspective on Fairness
Michael Pum-Shin Kim · 2020
Closest in time.
Sample complexity of uniform convergence for multicalibration
Eliran Shabat, Lee Cohen, and Yishay Mansour · 2020
Closest in time.
Individual calibration with randomized forecasting
Shengjia Zhao, Tengyu Ma, and Stefano Ermon · 2020
Closest in time.