Michael E. Saks

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Local Enumeration and Majority Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

On Randomized Reductions to the Random Strings.

[BibT_eX]

[DOI]

Rahul Santhanam

Electron. Colloquium Comput. Complex., 2022

2020

On the discrepancy of random matrices with many columns.

[BibT_eX]

[DOI]

Cole Franks

Random Struct. Algorithms, 2020

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.

[BibT_eX]

[DOI]

J. ACM, 2020

An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function.

[BibT_eX]

[DOI]

John Chiarelli

Pooya Hatami

Comb., 2020

Constant factor approximations to edit distance on far input pairs in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions.

[BibT_eX]

[DOI]

Rahul Santhanam

Proceedings of the 35th Computational Complexity Conference, 2020

2019

On Online Labeling with Large Label Set.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

2018

Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function.

[BibT_eX]

[DOI]

John Chiarelli

Pooya Hatami

CoRR, 2018

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.

[BibT_eX]

[DOI]

Debarati Das

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Online Labeling: Algorithms, Lower Bounds and Open Questions.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

A Communication Game Related to the Sensitivity Conjecture.

[BibT_eX]

[DOI]

Justin Gilmer

Theory Comput., 2017

Estimating the Longest Increasing Sequence in Polylogarithmic Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance.

[BibT_eX]

[DOI]

Timothy Naumovitz

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Hellinger volume and number-on-the-forehead communication complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Noisy population recovery in polynomial time.

[BibT_eX]

[DOI]

Anindya De

Sijian Tang

Electron. Colloquium Comput. Complex., 2016

Composition limits and separating examples for some boolean function complexity measures.

[BibT_eX]

[DOI]

Justin Gilmer

Srikanth Srinivasan

Comb., 2016

2015

Tight Lower Bounds for the Online Labeling Problem.

[BibT_eX]

[DOI]

Jan Bulánek

SIAM J. Comput., 2015

A tail bound for read-k families of functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2015

Efficient indexing of necklaces and irreducible polynomials over finite fields.

[BibT_eX]

[DOI]

Swastik Kopparty

Mrinal Kumar

Electron. Colloquium Comput. Complex., 2015

Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2015

A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity.

[BibT_eX]

[DOI]

Timothy Naumovitz

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

A New Approach to the Sensitivity Conjecture.

[BibT_eX]

[DOI]

Justin Gilmer

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

The Power of Super-logarithmic Number of Players.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2014

2013

On the practically interesting instances of MAXCUT.

[BibT_eX]

[DOI]

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

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance.

[BibT_eX]

[DOI]

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

On Randomized Online Labeling with Polynomially Many Labels.

[BibT_eX]

[DOI]

Jan Bulánek

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

A Polynomial Time Algorithm for Lossy Population Recovery.

[BibT_eX]

[DOI]

Ankur Moitra

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

2012

A Tail Bound for Read-k Families of Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Clustering is difficult only when it does not matter

[BibT_eX]

[DOI]

Amit Daniely

Nati Linial

CoRR, 2012

On Online Labeling with Polynomially Many Labels.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

The Dual BKR Inequality and Rudich's Conjecture.

[BibT_eX]

[DOI]

Clifford D. Smyth

Comb. Probab. Comput., 2011

An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times.

[BibT_eX]

[DOI]

Srikrishnan Divakaran

Algorithmica, 2011

2010

Rounds vs. Queries Tradeoff in Noisy Computation.

[BibT_eX]

[DOI]

Theory Comput., 2010

Local Monotonicity Reconstruction.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions.

[BibT_eX]

[DOI]

Nikos Leonardos

Comput. Complex., 2010

Local Property Reconstruction and Monotonicity.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

2009

The unlabelled speed of a hereditary graph property.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2009

2008

Backtracking Based k-SAT Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower Bounds for the Noisy Broadcast Problem.

[BibT_eX]

[DOI]

Guy Kindler

SIAM J. Comput., 2008

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Approximation algorithms for problems in scheduling with set-ups.

[BibT_eX]

[DOI]

Srikrishnan Divakaran

Discret. Appl. Math., 2008

Online multicast with egalitarian cost sharing.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Parallel monotonicity reconstruction.

[BibT_eX]

[DOI]

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

2007

Probabilistic strategies for the partition and plurality problems.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2007

2006

A localization inequality for set functions.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2006

Competitive auctions.

[BibT_eX]

[DOI]

Games Econ. Behav., 2006

The Non-Crossing Graph.

[BibT_eX]

[DOI]

David Statter

Electron. J. Comb., 2006

Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

A parallel search game.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2005

An improved exponential-time algorithm for k-SAT.

[BibT_eX]

[DOI]

J. ACM, 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Every decision tree has an influential variable

[BibT_eX]

[DOI]

CoRR, 2005

Three Optimal Algorithms for Balls of Three Colors.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Rounds vs queries trade-off in noisy computation.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Weak monotonicity suffices for truthfulness on convex domains.

[BibT_eX]

[DOI]

Lan Yu

Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

Every decision tree has an in.uential variable.

[BibT_eX]

[DOI]

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

2004

A lower bound on the quantum query complexity of read-once functions.

[BibT_eX]

[DOI]

Howard Barnum

J. Comput. Syst. Sci., 2004

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.

[BibT_eX]

[DOI]

Alex Samorodnitsky

Leonid Zosin

Comb., 2004

Multicolour Turán problems.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2004

A Lower Bound on the Competitive Ratio of Truthful Auctions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

2003

Time-space trade-off lower bounds for randomized computation of decision problems.

[BibT_eX]

[DOI]

J. ACM, 2003

The Euclidean Distortion of Complete Binary Trees.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2003

Complexity of some arithmetic problems for binary polynomials.

[BibT_eX]

[DOI]

Eric Allender

Anna Bernasconi

Carsten Damm

Joachim von zur Gathen

Igor E. Shparlinski

Comput. Complex., 2003

Optimal Separation of EROW and CROWPRAMs.

[BibT_eX]

[DOI]

Srinivasan Venkatesh

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Quantum query complexity and semi-definite programming.

[BibT_eX]

[DOI]

Howard Barnum

Mario Szegedy

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

On list update and work function algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.

[BibT_eX]

[DOI]

Alexander Russell

David Zuckerman

SIAM J. Comput., 2002

The Efficiency of Resolution and Davis--Putnam Procedures.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

Kleitman and combinatorics.

[BibT_eX]

[DOI]

Discret. Math., 2002

Space lower bounds for distance approximation in the data stream model.

[BibT_eX]

[DOI]

Xiaodong Sun

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Time-Space Tradeoffs for Branching Programs.

[BibT_eX]

[DOI]

Paul Beame

T. S. Jayram

J. Comput. Syst. Sci., 2001

A Lower Bound for Primality.

[BibT_eX]

[DOI]

Eric Allender

Igor E. Shparlinski

J. Comput. Syst. Sci., 2001

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols.

[BibT_eX]

[DOI]

Algorithmica, 2001

2000

Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge.

[BibT_eX]

[DOI]

Fotios Zaharoglou

SIAM J. Comput., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Low discrepancy sets yield approximate min-wise independent permutation families.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Exponential lower bounds for depth three Boolean circuits.

[BibT_eX]

[DOI]

Francis Zane

Comput. Complex., 2000

A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture.

[BibT_eX]

[DOI]

Cliff Smyth

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Products and Help Bits in Decision Trees.

[BibT_eX]

[DOI]

Noam Nisan

Steven Rudich

SIAM J. Comput., 1999

BP HSpace(S) subseteq DSPACE(S3/2).

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Optimal Space Distributed Order-Preserving Lists.

[BibT_eX]

[DOI]

Fotios Zaharoglou

J. Algorithms, 1999

1998

Explicit OR-Dispersers with Polylogarithmic Degree.

[BibT_eX]

[DOI]

Aravind Srinivasan

J. ACM, 1998

Trees and Euclidean Metrics.

[BibT_eX]

[DOI]

Avner Magen

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Size-Depth Tradeoffs for Threshold Circuits.

[BibT_eX]

[DOI]

Russell Impagliazzo

SIAM J. Comput., 1997

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.

[BibT_eX]

[DOI]

Comb., 1997

Exponential Lower Bounds for Depth 3 Boolean Circuits.

[BibT_eX]

[DOI]

Francis Zane

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Witness Sets for Families of Binary Vectors.

[BibT_eX]

[DOI]

J. Comb. Theory A, 1996

Local Management of a Global Resource in a Communication Network.

[BibT_eX]

[DOI]

J. ACM, 1996

Randomized Robot Navigation Algorithms.

[BibT_eX]

[DOI]

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

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Randomization and Derandomization in Space_Bounded Computation.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

On the bandwidth of triangulated triangles.

[BibT_eX]

[DOI]

Robert Hochberg

Colin McDiarmid

Discret. Math., 1995

Explicit dispersers with polylog degree.

[BibT_eX]

[DOI]

Aravind Srinivasan

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

RSPACE(S) \subseteq DSPACE(S3/2).

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Approximating Threshold Circuits by Rational Functions

[BibT_eX]

[DOI]

Inf. Comput., August, 1994

A Complexity Index for Satisfiability Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Non-Deterministic Communication Complexity with Few Witnesses.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

1993

The Number of Distinct Subset Sums of a Finite Set of Vectors.

[BibT_eX]

Ernest F. Brickell

J. Comb. Theory A, 1993

Communication Complexity and Combinatorial Lattice Theory.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1993

Combinatorial characterization of read-once formulae.

[BibT_eX]

[DOI]

Discret. Math., 1993

Correlation inequalities and a conjecture for permanents.

[BibT_eX]

[DOI]

Yosef Rinott

Comb., 1993

Low diameter graph decompositions.

[BibT_eX]

[DOI]

Comb., 1993

Size-depth trade-offs for threshold circuits.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Sphere Packing and Local Majorities in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992

An Optimal On-Line Algorithm for Metrical Task System.

[BibT_eX]

[DOI]

Allan Borodin

J. ACM, 1992

Sharpening the LYM inequality.

[BibT_eX]

[DOI]

Comb., 1992

Adapting to Asynchronous Dynamic Networks (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

A Decomposition Theorem and Bounds for Randomized Server Problems

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Non-deterministic Communication Complexity with Few Witness.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

On computing majority by comparisons.

[BibT_eX]

[DOI]

Michael Werman

Comb., 1991

Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice.

[BibT_eX]

[DOI]

Nir Shavit

Heather Woll

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Decomposing Graphs into Regions of Small Diameter.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Optimal Space Distributed Move-to-Front Lists.

[BibT_eX]

[DOI]

Fotios Zaharoglou

Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

1990

On Threshold Circuits for Parity

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Dining Philosophers Algorithm with Polynomial Response Time

[BibT_eX]

[DOI]

Baruch Awerbuch

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On Threshold Circuits for Parity (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989

A Robust Noncryptographic Protocol for Collective Coin Flipping.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1989

The periodic balanced sorting network.

[BibT_eX]

[DOI]

J. ACM, 1989

An on-line graph coloring algorithm with sublinear performance ratio.

[BibT_eX]

[DOI]

William T. Trotter

Discret. Math., 1989

Some extremal problems arising form discrete control processes.

[BibT_eX]

[DOI]

David Lichtenstein

Comb., 1989

A dynamic location problem for graphs.

[BibT_eX]

[DOI]

Fan R. K. Chung

Ronald L. Graham

Comb., 1989

The Cell Probe Complexity of Dynamic Data Structures

[BibT_eX]

[DOI]

Michael L. Fredman

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

A Limit Theorem for (min, +) Matrix Multiplication.

[BibT_eX]

[DOI]

Math. Oper. Res., 1988

An intersection problem for finite automata.

[BibT_eX]

[DOI]

Rick Statman

Discret. Appl. Math., 1988

Lattices, Möbius Functions and Communication Complexity

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.

[BibT_eX]

[DOI]

J. Graph Theory, 1987

Every finite distributive lattice is a set of stable matchings for a small stable marriage instance.

[BibT_eX]

[DOI]

J. Comb. Theory A, 1987

On the widths of finite distributive lattices.

[BibT_eX]

[DOI]

Discret. Math., 1987

The smallets n-uniform hypergraph with positive discrepancy.

[BibT_eX]

[DOI]

Comb., 1987

Imperfect Random Sources and Discrete Controlled Processes

[BibT_eX]

[DOI]

David Lichtenstein

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

An Optimal Online Algorithm for Metrical Task Systems

[BibT_eX]

[DOI]

Allan Borodin

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Detecting Global Termination Conditions in the Face of Uncertainty.

[BibT_eX]

[DOI]

Yehuda Afek

Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

1986

Maximum induced trees in graphs.

[BibT_eX]

[DOI]

Paul Erdös

Vera T. Sós

J. Comb. Theory B, 1986

Some sequences associated with combinatorial structures.

[BibT_eX]

[DOI]

Discret. Math., 1986

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

On a Search Problem Related to Branch-and-Bound Procedures

[BibT_eX]

[DOI]

Richard M. Karp

Avi Wigderson

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Every Poset Has a Central Element.

[BibT_eX]

[DOI]

J. Comb. Theory A, 1985

Searching Ordered Structures.

[BibT_eX]

[DOI]

J. Algorithms, 1985

1984

A topological approach to evasiveness.

[BibT_eX]

[DOI]

Dean Sturtevant

Comb., 1984

A polyomino with no stochastic function.

[BibT_eX]

[DOI]

Comb., 1984

Every Poset Has a Good Comparison

[BibT_eX]

[DOI]

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

Largest digraphs contained in all n-tournaments.

[BibT_eX]

[DOI]

Vera T. Sós

Comb., 1983

The Balanced Sorting Network.

[BibT_eX]

[DOI]

Martin Dowd

Yehoshua Perl

Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983

Information Bounds Are Good for Search Problems on Ordered Data Structures

[BibT_eX]

[DOI]

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1980

Dilworth Numbers, Incidence Maps and Product Partial Orders.

[BibT_eX]

[DOI]

SIAM J. Algebraic Discret. Methods, 1980

Product partial orders with the sperner property.

[BibT_eX]

[DOI]

Robert A. Proctor

Dean G. Sturtevant

Discret. Math., 1980

1979

Group labelings of graphs.

[BibT_eX]

[DOI]

Paul H. Edelman