Mark Braverman

Proceedings of the 37th International Conference on Machine Learning, 2020

The Role of Randomness and Noise in Strategic Classification.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Foundations of Responsible Computing, 2020

The Gradient Complexity of Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

The Price of Uncertain Priors in Source Coding.

[BibT_eX]

[DOI]

Brendan Juba

IEEE Trans. Inf. Theory, 2019

On Rich $2$-to-$1$ Games.

[BibT_eX]

[DOI]

Subhash Khot

Dor Minzer

Electron. Colloquium Comput. Complex., 2019

Reliable communication over highly connected noisy networks.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility.

[BibT_eX]

[DOI]

CoRR, 2019

Space-bounded Church-Turing thesis and computational tractability of closed systems.

[BibT_eX]

[DOI]

Cristobal Rojas

Jonathan Schneider

CoRR, 2019

On the Computational Power of Radio Channels.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Multi-armed Bandit Problems with Strategic Arms.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Sorted Top-k in Rounds.

[BibT_eX]

[DOI]

Yuval Peres

Proceedings of the Conference on Learning Theory, 2019

2018

Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Interactive compression to external information.

[BibT_eX]

[DOI]

Gillat Kol

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

On Simultaneous Two-player Combinatorial Auctions.

[BibT_eX]

[DOI]

S. Matthew Weinberg

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Selling to a No-Regret Buyer.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

A Candidate for a Strong Separation of Information and Communication.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Semi-Direct Sum Theorem and Nearest Neighbor under l_infty.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Nash Equilibria in Perturbation-Stable Games.

[BibT_eX]

[DOI]

Theory Comput., 2017

Coding for Interactive Communication Correcting Insertions and Deletions.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2017

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise.

[BibT_eX]

[DOI]

Klim Efremenko

SIAM J. Comput., 2017

Information Value of Two-Prover Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs.

[BibT_eX]

[DOI]

Gil Cohen

Electron. Colloquium Comput. Complex., 2017

Strategyproof Mechanisms for Competitive Influence in Networks.

[BibT_eX]

[DOI]

Algorithmica, 2017

Communication Requirements and Informative Signaling in Matching Markets.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All.

[BibT_eX]

[DOI]

Ariel Schvartzman

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness.

[BibT_eX]

[DOI]

Rotem Oshman

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Optimal Provision-After-Wait in Healthcare.

[BibT_eX]

[DOI]

Jing Chen

Sampath Kannan

Math. Oper. Res., 2016

Optimal Resilience for Short-Circuit Noise in Formulas.

[BibT_eX]

[DOI]

Ran Gelles

Michael A. Yitayew

Electron. Colloquium Comput. Complex., 2016

Network coding in undirected graphs is either very helpful or not helpful at all.

[BibT_eX]

[DOI]

Ariel Schvartzman

CoRR, 2016

Guest Editorial for Information Complexity and Applications.

[BibT_eX]

[DOI]

David P. Woodruff

Algorithmica, 2016

Parallel algorithms for select and partition with noisy comparisons.

[BibT_eX]

[DOI]

S. Matthew Weinberg

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Communication lower bounds for statistical estimation problems via a distributed data processing inequality.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions.

[BibT_eX]

[DOI]

S. Matthew Weinberg

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Interactive Information Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Information complexity is computable.

[BibT_eX]

[DOI]

Jon Schneider

Electron. Colloquium Comput. Complex., 2015

The Communication Complexity of Number-In-Hand Set Disjointness with No Promise.

[BibT_eX]

[DOI]

Rotem Oshman

Electron. Colloquium Comput. Complex., 2015

ETH Hardness for Densest-k-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Constant-rate coding for multiparty interactive communication is impossible.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Tight space-noise tradeoffs in computing the ergodic measure.

[BibT_eX]

[DOI]

Cristobal Rojas

Jon Schneider

CoRR, 2015

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

CoRR, 2015

An Interactive Information Odometer and Applications.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On Information Complexity in the Broadcast Model.

[BibT_eX]

[DOI]

Rotem Oshman

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

The price of uncertainty in communication.

[BibT_eX]

[DOI]

Brendan Juba

Proceedings of the 53rd Annual Allerton Conference on Communication, 2015

2014

Toward Coding for Maximum Errors in Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Information Equals Amortized Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Pseudorandom Generators for Regular Branching Programs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Stability in Large Matching Markets with Complementarities.

[BibT_eX]

[DOI]

Itai Ashlagi

Avinatan Hassidim

Oper. Res., 2014

An Interactive Information Odometer with Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

The computational hardness of pricing compound options.

[BibT_eX]

[DOI]

Kanika Pasricha

Electron. Colloquium Comput. Complex., 2014

Simulating Noisy Channel Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Small value parallel repetition for general games.

[BibT_eX]

[DOI]

Ankit Garg

Electron. Colloquium Comput. Complex., 2014

Contracting Experts With Unknown Cost Structures.

[BibT_eX]

[DOI]

Gal Oshri

CoRR, 2014

2013

Inapproximability of NP-Complete Variants of Nash Equilibrium.

[BibT_eX]

[DOI]

Per Austrin

Eden Chlamtac

Theory Comput., 2013

How to Compress Interactive Communication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009).

[BibT_eX]

[DOI]

Daniel A. Spielman

SIAM J. Comput., 2013

Direct product via round-preserving compression.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Public vs private coin in bounded-round information.

[BibT_eX]

[DOI]

Ankit Garg

Electron. Colloquium Comput. Complex., 2013

Tight Bounds for Set Disjointness in the Message Passing Model

[BibT_eX]

[DOI]

CoRR, 2013

Computing with real numbers, from Archimedes to Turing and beyond.

[BibT_eX]

[DOI]

Commun. ACM, 2013

Search using queries on indistinguishable items.

[BibT_eX]

[DOI]

Gal Oshri

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Finding Endogenously Formed Communities.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On the convergence of the Hegselmann-Krause system.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

A Tight Bound for Set Disjointness in the Message-Passing Model.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Noise versus Computational Intractability in Dynamics.

[BibT_eX]

[DOI]

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

A hard-to-compress interactive task?

[BibT_eX]

[DOI]

Proceedings of the 51st Annual Allerton Conference on Communication, 2013

2012

Pebbles and Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

An Information Complexity Approach to Extended Formulations.

[BibT_eX]

[DOI]

Ankur Moitra

Electron. Colloquium Comput. Complex., 2012

Information lower bounds via self-reducibility.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

From Information to Exact Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Truthful Mechanisms for Competing Submodular Processes

[BibT_eX]

[DOI]

CoRR, 2012

I Like Her more than You: Self-determined Communities

[BibT_eX]

[DOI]

CoRR, 2012

Noise vs computational intractability in dynamics.

[BibT_eX]

[DOI]

Alexander Grigo

Cristobal Rojas

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Coding for interactive computation: Progress and challenges.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual Allerton Conference on Communication, 2012

2011

A discrepancy lower bound for information complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Towards deterministic tree code constructions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Poly-logarithmic independence fools bounded-depth boolean circuits.

[BibT_eX]

[DOI]

Commun. ACM, 2011

Matching with couples revisited.

[BibT_eX]

[DOI]

Itai Ashlagi

Avinatan Hassidim

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Leaky Pseudo-Entropy Functions.

[BibT_eX]

[DOI]

Avinatan Hassidim

Yael Tauman Kalai

Proceedings of the Innovations in Computer Science, 2011

The Grothendieck Constant is Strictly Smaller than Krivine's Bound.

[BibT_eX]

[DOI]

Konstantin Makarychev

Yury Makarychev

Assaf Naor

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Polylogarithmic independence fools AC0 circuits.

[BibT_eX]

[DOI]

J. ACM, 2010

Towards Coding for Maximum Errors in Interactive Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Efficient Communication Using Partial Information.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Approximate Nash Equilibria under Stability Conditions

[BibT_eX]

[DOI]

CoRR, 2010

2009

Poly-logarithmic independence fools AC0 circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Direct Sums in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Sorting from Noisy Information

[BibT_eX]

[DOI]

Elchanan Mossel

CoRR, 2009

Space-Efficient Counting in Graphs on Surfaces.

[BibT_eX]

[DOI]

Raghav Kulkarni

Sambuddha Roy

Comput. Complex., 2009

The complexity of simulating Brownian Motion.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Fractional Pebbling and Thrifty Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Finding Low Error Clusterings.

[BibT_eX]

[DOI]

Proceedings of the COLT 2009, 2009

Poly-logarithmic Independence Fools AC0 Circuits.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Computability and Complexity of Julia Sets (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 2009

Computability of Julia Sets.

[BibT_eX]

Algorithms and computation in mathematics 23, Springer, ISBN: 978-3-540-68546-3, 2009

2008

Computability and complexity of Julia sets.

[BibT_eX]

[DOI]

PhD thesis, 2008

The complexity of properly learning simple concept classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Noisy sorting without resampling.

[BibT_eX]

[DOI]

Elchanan Mossel

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On ad hoc routing with guaranteed delivery.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2007

Filled Julia Sets with Empty Interior Are Computable.

[BibT_eX]

[DOI]

Found. Comput. Math., 2007

Parity Problems in Planar Graphs.

[BibT_eX]

[DOI]

Raghav Kulkarni

Sambuddha Roy

Electron. Colloquium Comput. Complex., 2007

Constructing non-computable Julia sets.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Derandomization of Euclidean Random Walks.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Termination of Integer Linear Programs.

[BibT_eX]

[DOI]

Proceedings of the Computer Aided Verification, 18th International Conference, 2006

2005

On computational complexity of Riemann mapping

[BibT_eX]

[DOI]

CoRR, 2005

On computational complexity of Siegel Julia sets

[BibT_eX]

[DOI]

CoRR, 2005

Computing over the Reals: Foundations for Scientific Computing

[BibT_eX]

[DOI]

Stephen A. Cook

CoRR, 2005

On the Complexity of Real Functions.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Hyperbolic Julia Sets are Poly-Time Computable.

[BibT_eX]

[DOI]

Proceedings of the 6th Workshop on Computability and Complexity in Analysis, 2004

Non-computable Julia sets

[BibT_eX]

[DOI]

CoRR, 2004

Learnability and Automatizability.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2001

A Monte Carlo Algorithm for a Lottery Problem.

[BibT_eX]

[DOI]