Papers: Ilias Diakonikolas

Algorithms and Optimization

· An Optimal Algorithm for the Efficient Approximation of Convex Pareto Curves
I. Diakonikolas, M. Yannakakis.
In preparation, 2009.

· How good is the Chord Algorithm?
C. Daskalakis, I. Diakonikolas, M. Yannakakis.
SODA 2010.

· Succinct Approximate Convex Pareto Curves
I. Diakonikolas, M. Yannakakis.
SODA 2008.

· Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
I. Diakonikolas, M. Yannakakis.
SIAM Journal on Computing, 2009. Conference version in APPROX 2007.

Complexity and Learning

· Bounded Independence Fools degree-2 Threshold Functions
I. Diakonikolas, D. Kane, J. Nelson.
Manuscript, 2009.

· Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions
I. Diakonikolas, P. Raghavendra, R. Servedio, L.-Y. Tan.
Manuscript, 2009.

· A Regularity Lemma, and low-weight approximators, for low-degree Polynomial Threshold Functions
I. Diakonikolas, R. Servedio, L.-Y. Tan, A. Wan.
Manuscript, 2009.

· Hardness of Agnostically Learning Halfspaces by degree-2 Threshold Functions
I. Diakonikolas, R. O’Donnell, R. Servedio, Y. Wu.
Manuscript, 2009.

· Bounded Independence Fools Halfspaces
I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, E. Viola.
FOCS 2009.

· Improved Approximation of Linear Threshold Functions
I. Diakonikolas, R. Servedio.
CCC 2009.

Property Testing

· Testing for Concise Representations
I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, A. Wan.
FOCS 2007.

· Efficiently Testing Sparse GF(2) Polynomials
I. Diakonikolas, H. Lee, K. Matulef, R. Servedio, A. Wan.
ICALP 2008.

Miscellaneous

· Optimal Node Placement for Path Disjoint Monitoring
L. Breslau, I. Diakonikolas, N. Duffield, Y. Gu, M. Hajiaghayi, D.S. Johnson, H. Karloff, M. Resende, S. Sen.
Submitted, 2008.

Back to main page