Avrim Blum

According to our database1, Avrim Blum
  • authored at least 221 papers between 1988 and 2018.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 2007, "For contributions to learning theory and algorithms.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On Price versus Quality.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017
Approximate Convex Hull of Data Streams.
CoRR, 2017

Active Tolerant Testing.
CoRR, 2017

Lifelong Learning in Costly Feature Spaces.
CoRR, 2017

Efficient PAC Learning from the Crowd.
CoRR, 2017

Opting Into Optimal Matchings.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Collaborative PAC Learning.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Efficient Co-Training of Linear Separators under Weak Dependence.
Proceedings of the 30th Conference on Learning Theory, 2017

Efficient PAC Learning from the Crowd.
Proceedings of the 30th Conference on Learning Theory, 2017

Lifelong Learning in Costly Feature Spaces.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016
Semi-supervised Learning.
Encyclopedia of Algorithms, 2016

Generalized Topic Modeling.
CoRR, 2016

Opting Into Optimal Matchings.
CoRR, 2016

Sparse Approximation via Generating Point Sets.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Computational Hardness of Manipulating Pairwise Voting Rules.
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015
Sparse Approximation via Generating Point Sets.
CoRR, 2015

The Ladder: A Reliable Leaderboard for Machine Learning Competitions.
CoRR, 2015

Special Issue on New Theoretical Challenges in Machine Learning.
Algorithmica, 2015

Online Allocation and Pricing with Economies of Scale.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Commitment Without Regrets: Online Learning in Stackelberg Security Games.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Variational Dropout and the Local Reparameterization Trick.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Privacy-Preserving Public Information for Sequential Games.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

The Ladder: A Reliable Leaderboard for Machine Learning Competitions.
Proceedings of the 32nd International Conference on Machine Learning, 2015

Efficient Representations for Lifelong Learning and Autoencoding.
Proceedings of The 28th Conference on Learning Theory, 2015

Learning Valuation Distributions from Partial Observation.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Privacy-Preserving Public Information for Sequential Games.
CoRR, 2014

Learning What's going on: reconstructing preferences and priorities from opaque transactions.
CoRR, 2014

Learning Valuation Distributions from Partial Observation.
CoRR, 2014

Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries.
CoRR, 2014

Efficient Representations for Life-Long Learning and Autoencoding.
CoRR, 2014

Active Learning and Best-Response Dynamics.
CoRR, 2014

Learning Mixtures of Ranking Models.
CoRR, 2014

Estimating Accuracy from Unlabeled Data.
Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, 2014

Learning Optimal Commitment to Overcome Insecurity.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Active Learning and Best-Response Dynamics.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Learning Mixtures of Ranking Models.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Lazy Defenders Are Almost Optimal against Diligent Attackers.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
The Price of Uncertainty.
ACM Trans. Economics and Comput., 2013

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
SIAM J. Comput., 2013

A learning theory approach to noninteractive database privacy.
J. ACM, 2013

Clustering under approximation stability.
J. ACM, 2013

Harnessing the power of two crossmatches.
Proceedings of the ACM Conference on Electronic Commerce, 2013

Learnability of DNF with representation-specific queries.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Differentially private data analysis of social networks via restricted sensitivity.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Exploiting Ontology Structures and Unlabeled Data for Learning.
Proceedings of the 30th International Conference on Machine Learning, 2013

Fast Private Data Release Algorithms for Sparse Queries.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Distributed Learning, Communication Complexity and Privacy.
Proceedings of the COLT 2012, 2012

Center-based clustering under perturbation stability.
Inf. Process. Lett., 2012

Differentially Private Data Analysis of Social Networks via Restricted Sensitivity
CoRR, 2012

Additive Approximation for Near-Perfect Phylogeny Construction
CoRR, 2012

Distributed Learning, Communication Complexity and Privacy
CoRR, 2012

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
CoRR, 2012

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Active Property Testing.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Additive Approximation for Near-Perfect Phylogeny Construction.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Fast Private Data Release Algorithms for Sparse Queries
CoRR, 2011

Active Testing
CoRR, 2011

Welfare and Profit Maximization with Production Costs
CoRR, 2011

A Learning Theory Approach to Non-Interactive Database Privacy
CoRR, 2011

Welfare and Profit Maximization with Production Costs.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games.
Theory of Computing, 2010

A discriminative model for semi-supervised learning.
J. ACM, 2010

Center-based Clustering under Perturbation Stability
CoRR, 2010

On Nash-Equilibria of Approximation-Stable Games.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

Trading off Mistakes and Don't-Know Predictions.
Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior.
Proceedings of the Innovations in Computer Science, 2010

Stability Yields a PTAS for k-Median and k-Means Clustering.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Improved Guarantees for Agnostic Learning of Disjunctions.
Proceedings of the COLT 2010, 2010

2009
Veritas: Combining Expert Opinions without Labeled Data.
International Journal on Artificial Intelligence Tools, 2009

Improved equilibria via public service advertising.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximate clustering without the approximation.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

The price of uncertainty.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Tracking Dynamic Sources of Malicious Activity at Internet Scale.
Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

2008
Item pricing for revenue maximization.
SIGecom Exchanges, 2008

A theory of learning with similarity functions.
Machine Learning, 2008

Reducing mechanism design to algorithm design via machine learning.
J. Comput. Syst. Sci., 2008

A learning theory approach to non-interactive database privacy.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Regret minimization and the price of total anarchy.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A discriminative framework for clustering via similarity functions.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Item pricing for revenue maximization.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Limits of Learning-based Signature Generation with Adversaries.
Proceedings of the Network and Distributed System Security Symposium, 2008

Veritas: Combining Expert Opinions without Labeled Data.
Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2008), 2008

Improved Guarantees for Learning via Similarity Functions.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

Clustering with Interactive Feedback.
Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007
Approximation Algorithms and Online Mechanisms for Item Pricing.
Theory of Computing, 2007

Mechanism design, machine learning, and pricing problems.
SIGecom Exchanges, 2007

Approximation Algorithms for Orienteering and Discounted-Reward TSP.
SIAM J. Comput., 2007

Introduction to the special issue on COLT 2006.
Machine Learning, 2007

From External to Internal Regret.
Journal of Machine Learning Research, 2007

A Theory of Loss-Leaders: Making Money by Pricing Below Cost.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Separating Populations with Wide Data: A Spectral Analysis.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

A Theory of Similarity Functions for Learning and Clustering.
Proceedings of the Discovery Science, 10th International Conference, 2007

Open Problems in Efficient Semi-supervised PAC Learning.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

A Theory of Similarity Functions for Learning and Clustering.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
Kernels as features: On kernels, margins, and low-dimensional mappings.
Machine Learning, 2006

Online algorithms for market clearing.
J. ACM, 2006

Approximation algorithms and online mechanisms for item pricing.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

On a theory of learning with similarity functions.
Proceedings of the Machine Learning, 2006

Black Box Anomaly Detection: Is It Utopian?.
Proceedings of the 5th ACM Workshop on Hot Topics in Networks, 2006

A Random-Surfer Web-Graph Model.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005
Combining Online Algorithms for Acceptance and Rejection.
Theory of Computing, 2005

Near-optimal online auctions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Random Projection, Margins, Kernels, and Feature-Selection.
Proceedings of the Subspace, 2005

Practical privacy: the SuLQ framework.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

New Streaming Algorithms for Fast Detection of Superspreaders.
Proceedings of the Network and Distributed System Security Symposium, 2005

Mechanism Design via Machine Learning.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

From External to Internal Regret.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

A PAC-Style Model for Learning from Labeled and Unlabeled Data.
Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004
Online learning in online auctions.
Theor. Comput. Sci., 2004

Correlation Clustering.
Machine Learning, 2004

Preference Elicitation and Query Learning.
Journal of Machine Learning Research, 2004

Approximation algorithms for deadline-TSP and vehicle routing with time-windows.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Detection of Interactive Stepping Stones: Algorithms and Confidence Bounds.
Proceedings of the Recent Advances in Intrusion Detection: 7th International Symposium, 2004

Co-Training and Expansion: Towards Bridging Theory and Practice.
Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Semi-supervised learning using randomized mincuts.
Proceedings of the Machine Learning, 2004

Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

On Kernels, Margins, and Low-Dimensional Mappings.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003
Microchoice Bounds and Self Bounding Learning Algorithms.
Machine Learning, 2003

Noise-tolerant learning, the parity problem, and the statistical query model.
J. ACM, 2003

Admission Control to Minimize Rejections.
Internet Mathematics, 2003

On Statistical Query Sampling and NMR Quantum Computing
Electronic Colloquium on Computational Complexity (ECCC), 2003

Static Optimality and Dynamic Search-Optimality in Lists and Trees.
Algorithmica, 2003

Online oblivious routing.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Combining online algorithms for rejection and acceptance.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Online learning in online auctions.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

On polynomial-time preference elicitation with value queries.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Planning in the Presence of Cost Functions Controlled by an Adversary.
Proceedings of the Machine Learning, 2003

Approximation Algorithms for Orienteering and Discounted-Reward TSP.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Machine Learning: My Favorite Results, Directions, and Open Problems.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Scheduling for Flow-Time with Admission Control.
Proceedings of the Algorithms, 2003

PAC-MDL Bounds.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Preference Elicitation and Query Learning.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

Learning a Function of r Relevant Variables.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

On Statistical Query Sampling and NMR Quantum Computing.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Online algorithms for market clearing.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Smoothed analysis of the perceptron algorithm for linear programming.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Static optimality and dynamic search-optimality in lists and trees.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Correlation Clustering.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Admission Control to Minimize Rejections.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Learning from Labeled and Unlabeled Data using Graph Mincuts.
Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28, 2001

2000
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
SIAM J. Comput., 2000

An Online Algorithm for Improving Performance in Navigation.
SIAM J. Comput., 2000

On-line Learning and the Metrical Task System Problem.
Machine Learning, 2000

Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
CoRR, 2000

Noise-tolerant learning, the parity problem, and the statistical query model.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness.
Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29, 2000

1999
Universal Portfolios With and Without Transaction Costs.
Machine Learning, 1999

A Constant-Factor Approximation Algorithm for the k-MST Problem.
J. Comput. Syst. Sci., 1999

On-line algorithms for combining language models.
Proceedings of the 1999 IEEE International Conference on Acoustics, 1999

Finely-Competitive Paging.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Probabilistic Planning in the Graphplan Framework.
Proceedings of the Recent Advances in AI Planning, 5th European Conference on Planning, 1999

Microchoice Bounds and Self Bounding Learning Algorithms.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998
On a theory of computing symposia.
SIGACT News, 1998

A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.
SIAM J. Comput., 1998

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
SIAM J. Comput., 1998

On Learning Read-k-Satisfy-j DNF.
SIAM J. Comput., 1998

A Note on Learning from Multiple-Instance Examples.
Machine Learning, 1998

Learning with Unreliable Boundary Queries.
J. Comput. Syst. Sci., 1998

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Algorithmica, 1998

Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On Learning Monotone Boolean Functions.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Combining Labeled and Unlabeled Data with Co-Training.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997
Navigating in Unfamiliar Geometric Terrain.
SIAM J. Comput., 1997

Empirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain.
Machine Learning, 1997

Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution.
J. Comput. Syst. Sci., 1997

An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.
Inf. Process. Lett., 1997

Selection of Relevant Features and Examples in Machine Learning.
Artif. Intell., 1997

Fast Planning Through Planning Graph Analysis.
Artif. Intell., 1997

A polylog(n)-Competitive Algorithm for Metrical Task Systems.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Universal Portfolios With and Without Transaction Costs.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

On-line Learning and the Metrical Task System Problem.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Randomized Robot Navigation Algorithms.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

On-line Algorithms in Machine Learning.
Proceedings of the Online Algorithms, 1996

1995
Fast Learning of k-Term DNF Formulas with Queries.
J. Comput. Syst. Sci., 1995

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
J. Comput. Syst. Sci., 1995

Coloring Random and Semi-Random k-Colorable Graphs.
J. Algorithms, 1995

A constant-factor approximation for the k-MST problem in the plane.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Fast Planning Through Planning Graph Analysis.
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

Empirical Support for Winnow and Weighted-Majority Based Algorithms: Results on a Calendar Scheduling Domain.
Proceedings of the Machine Learning, 1995

Learning with Unreliable Boundary Queries.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain.
SIAM J. Comput., 1994

Linear Approximation of Shortest Superstrings.
J. ACM, 1994

New Approximation Algorithms for Graph Coloring.
J. ACM, 1994

On the minimum latency problem.
CoRR, 1994

An on-line algorithm for improving performance in navigation.
CoRR, 1994

Weakly learning DNF and characterizing statistical query learning using Fourier analysis.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The minimum latency problem.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On Learning Read-k-Satisfy-j DNF.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
Training a 3-Node Neural Network is NP-Complete.
Proceedings of the Machine Learning: From Theory to Applications, 1993

Learning an Intersection of k Halfspaces over a Uniform Distribution
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

An On-Line Algorithm for Improving Performance in Navigation
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Cryptographic Primitives Based on Hard Learning Problems.
Proceedings of the Advances in Cryptology, 1993

On Learning Embedded Symmetric Concepts.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Training a 3-node neural network is NP-complete.
Neural Networks, 1992

Learning Boolean Functions in an Infinite Attribute Space.
Machine Learning, 1992

Rank-r Decision Trees are a Subclass of r-Decision Lists.
Inf. Process. Lett., 1992

Fast Learning of k-Term DNF Formulas with Queries
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

A Decomposition Theorem and Bounds for Randomized Server Problems
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Learning Switching Concepts.
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991
Navigating in Unfamiliar Geometric Terrain (Preliminary Version)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Linear Approximation of Shortest Superstrings
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Navigating in Unfamiliar Geometric Terrain (Extended Summary).
Proceedings of the On-Line Algorithms, 1991

Learning in the Presence of Finitely or Infinitely Many Irrelevant Attributes.
Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

1990
Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Some Tools for Approximate 3-Coloring (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning Functions of k Terms.
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

Separating PAC and Mistake-Bound Learning Models Over the Boolean Domain (Abstract).
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Training a 3-Node Neural Network is NP-Complete.
Proceedings of the Advances in Neural Information Processing Systems 1, 1988

Training a 3-Node Neural Network is NP-Complete.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988


  Loading...