ACM Fellow 2016, "For contributions in the study of expander graphs, derandomization and streaming algorithms".
2024
Am. Math. Mon., November, 2024
Implicit Representation of Sparse Hereditary Families.
Discret. Comput. Geom., September, 2024
Invertibility of Digraphs and Tournaments.
SIAM J. Discret. Math., March, 2024
Turán graphs with bounded matching number.
J. Comb. Theory B, March, 2024
Eur. J. Comb., February, 2024
Logarithmically Larger Deletion Codes of All Distances.
IEEE Trans. Inf. Theory, January, 2024
Random Necklaces Require Fewer Cuts.
SIAM J. Discret. Math., 2024
Erratum: Multitasking Capacity: Hardness Results and Improved Constructions.
SIAM J. Discret. Math., 2024
Erasure list-decodable codes and Turán hypercube problems.
Finite Fields Their Appl., 2024
A Bicriterion Concentration Inequality and Prophet Inequalities for <i>k</i>-Fold Matroid Unions.
CoRR, 2024
Optimal Preprocessing for Answering On-Line Product Queries.
CoRR, 2024
Sumsets in the Hypercube.
CoRR, 2024
Sublinear Time Shortest Path in Expander Graphs.
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024
Optimal Sample Complexity of Contrastive Learning.
Proceedings of the Twelfth International Conference on Learning Representations, 2024
A Unified Characterization of Private Learnability via Graph Theory.
Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024
2023
The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs.
SIAM J. Discret. Math., December, 2023
New bounds on the maximum number of neighborly boxes in Rd.
Eur. J. Comb., December, 2023
Largest subgraph from a hereditary property in a random graph.
Discret. Math., September, 2023
Complete minors and average degree: A short proof.
J. Graph Theory, July, 2023
Structured Codes of Graphs.
SIAM J. Discret. Math., March, 2023
Comb. Probab. Comput., March, 2023
Boosting Simple Learners.
TheoretiCS, 2023
Typical and extremal aspects of friends-and-strangers graphs.
J. Comb. Theory B, 2023
On bipartite coverings of graphs and multigraphs.
CoRR, 2023
Strong blocking sets and minimal codes from expander graphs.
CoRR, 2023
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023
2022
Private and Online Learnability Are Equivalent.
J. ACM, 2022
On the hat guessing number of graphs.
Discret. Math., 2022
Discret. Comput. Geom., 2022
The diameter of the uniform spanning tree of dense graphs.
Comb. Probab. Comput., 2022
Identifying the Deviator.
CoRR, 2022
Additive Approximation of Generalized Turán Questions.
Algorithmica, 2022
2021
The Price of Bounded Preemption.
ACM Trans. Parallel Comput., 2021
Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs.
Exp. Math., 2021
Mixing properties of colourings of the ℤd lattice.
Comb. Probab. Comput., 2021
Partitioning all k-subsets into r-wise intersecting families.
CoRR, 2021
Explicit Expanders of Every Degree and Size.
Comb., 2021
Limitations on regularity lemmas for clustering graphs.
Adv. Appl. Math., 2021
Adversarial laws of large numbers and optimal regret in online classification.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Efficient Splitting of Necklaces.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
A Theory of PAC Learnability of Partial Concept Classes.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Distributed Corruption Detection in Networks.
Theory Comput., 2020
Multitasking Capacity: Hardness Results and Improved Constructions.
SIAM J. Discret. Math., 2020
Efficient Removal Lemmas for Matrices.
Order, 2020
Out-colourings of digraphs.
J. Graph Theory, 2020
The hat guessing number of graphs.
J. Comb. Theory B, 2020
On the product dimension of clique factors.
Eur. J. Comb., 2020
A probabilistic variant of Sperner 's theorem and of maximal r-cover free families.
Discret. Math., 2020
Isoperimetry, stability, and irredundance in direct products.
Discret. Math., 2020
Edge-statistics on large graphs.
Comb. Probab. Comput., 2020
Efficient Splitting of Measures and Necklaces.
CoRR, 2020
Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs.
CoRR, 2020
Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.
Comb., 2020
Closure Properties for Private Classification and Online Prediction.
Proceedings of the Conference on Learning Theory, 2020
Hierarchical Clustering: A 0.585 Revenue Approximation.
Proceedings of the Conference on Learning Theory, 2020
Palette Sparsification Beyond (Δ+1) Vertex Coloring.
Proceedings of the Approximation, 2020
2019
List-Decodable Zero-Rate Codes.
IEEE Trans. Inf. Theory, 2019
Dynamics of Evolving Social Groups.
ACM Trans. Economics and Comput., 2019
Induced Universal Hypergraphs.
SIAM J. Discret. Math., 2019
J. Lond. Math. Soc., 2019
H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups.
Discret. Math., 2019
Reliable communication over highly connected noisy networks.
Distributed Comput., 2019
On Generalized Regularity.
CoRR, 2019
High-girth near-Ramanujan graphs with localized eigenvectors.
CoRR, 2019
Private PAC learning implies finite Littlestone dimension.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Limits of Private Learning with Access to Public Data.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
2018
Redesigning the Israeli Medical Internship Match.
ACM Trans. Economics and Comput., 2018
Clique coloring of dense random graphs.
J. Graph Theory, 2018
Ramsey-nice families of graphs.
Eur. J. Comb., 2018
Uniformly Discrete Forests with Poor Visibility.
Comb. Probab. Comput., 2018
The Minrank of Random Graphs over Arbitrary Fields.
CoRR, 2018
2017
Duplication Distance to the Root for Binary Sequences.
IEEE Trans. Inf. Theory, 2017
Broadcast Transmission to Prioritizing Receivers.
SIAM J. Discret. Math., 2017
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback.
SIAM J. Comput., 2017
More on the Bipartite Decomposition of Random Graphs.
J. Graph Theory, 2017
Testing hereditary properties of ordered graphs and matrices.
Electron. Colloquium Comput. Complex., 2017
Revenue and Reserve Prices in a Probabilistic Single Item Auction.
Algorithmica, 2017
Optimal induced universal graphs for bounded-degree graphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
A graph-theoretic approach to multitasking.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
Optimal Compression of Approximate Inner Products and Dimension Reduction.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
Encyclopedia of Algorithms, 2016
Linear Boolean Classification, Coding and the Critical Problem.
IEEE Trans. Inf. Theory, 2016
On the Maximum Quartet Distance between Phylogenetic Trees.
SIAM J. Discret. Math., 2016
Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes.
J. Graph Theory, 2016
Many T copies in H-free graphs.
J. Comb. Theory B, 2016
High girth augmented trees are huge.
J. Comb. Theory A, 2016
Testing Equality in Communication Graphs.
Electron. Colloquium Comput. Complex., 2016
Local and global colorability of graphs.
Discret. Math., 2016
On Active and Passive Testing.
Comb. Probab. Comput., 2016
Removal Lemmas for Matrices.
CoRR, 2016
On the duplication distance of binary strings.
Proceedings of the IEEE International Symposium on Information Theory, 2016
Sign rank versus VC dimension.
Proceedings of the 29th Conference on Learning Theory, 2016
2015
How to Put Through Your Agenda in Collective Binary Decisions.
ACM Trans. Economics and Comput., 2015
Separation Dimension of Bounded Degree Graphs.
SIAM J. Discret. Math., 2015
Chasing a Fast Robber on Planar Graphs and Random Graphs.
J. Graph Theory, 2015
Comparable pairs in families of sets.
J. Comb. Theory B, 2015
Bipartite decomposition of random graphs.
J. Comb. Theory B, 2015
Practically stabilizing SWMR atomic memory in message-passing systems.
J. Comput. Syst. Sci., 2015
Size and Degree Anti-Ramsey Numbers.
Graphs Comb., 2015
Welfare Maximization with Limited Interaction.
Electron. Colloquium Comput. Complex., 2015
Easily Testable Graph Properties.
Comb. Probab. Comput., 2015
Corruption Detection on Networks.
CoRR, 2015
Drawing outerplanar graphs using three edge lengths.
Comput. Geom., 2015
Efficient Global Learning of Entailment Graphs.
Comput. Linguistics, 2015
On Rigid Matrices and U-Polynomials.
Comput. Complex., 2015
Local Correction with Constant Error Rate.
Algorithmica, 2015
How Robust Is the Wisdom of the Crowds?
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015
Online Learning with Feedback Graphs: Beyond Bandits.
Proceedings of The 28th Conference on Learning Theory, 2015
2014
On the Compatibility of Quartet Trees.
SIAM J. Discret. Math., 2014
Correction: Basic Network Creation Games.
SIAM J. Discret. Math., 2014
Maximizing the Number of Nonnegative Subsets.
SIAM J. Discret. Math., 2014
Two notions of unit distance graphs.
J. Comb. Theory A, 2014
Sign rank, VC dimension and spectral gaps.
Electron. Colloquium Comput. Complex., 2014
Chasing robbers on random geometric graphs - An alternative approach.
Discret. Appl. Math., 2014
Broadcast Throughput in Radio Networks: Routing vs. Network Coding.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Linear Boolean classification, coding and "the critical problem".
Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014
The Cover Number of a Matrix and its Algorithmic Applications.
Proceedings of the Approximation, 2014
2013
Adversarial Leakage in Games.
SIAM J. Discret. Math., 2013
Basic Network Creation Games.
SIAM J. Discret. Math., 2013
Minimizing the Number of Carries in Addition.
SIAM J. Discret. Math., 2013
Nearly Tight Bounds for Testing Function Isomorphism.
SIAM J. Comput., 2013
A Note on Degenerate and Spectrally Degenerate Graphs.
J. Graph Theory, 2013
The Turán number of sparse spanning graphs.
J. Comb. Theory B, 2013
Matrix sparsification and nested dissection over arbitrary fields.
J. ACM, 2013
Restricted Integer Partition Functions.
Integers, 2013
The chromatic number of random Cayley graphs.
Eur. J. Comb., 2013
Beeping a maximal independent set.
Distributed Comput., 2013
On sunflowers and matrix multiplication.
Comput. Complex., 2013
The Asymmetric Matrix Partition Problem.
Proceedings of the Web and Internet Economics - 9th International Conference, 2013
The approximate rank of a matrix and its algorithmic applications: approximate rank.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Differential pricing with inequity aversion in social networks.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013
From Bandits to Experts: A Tale of Domination and Independence.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013
The Value of Ignorance about the Number of Players.
Proceedings of the Late-Breaking Developments in the Field of Artificial Intelligence, 2013
Bundling Attacks in Judgment Aggregation.
Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013
Neighborly Families of Boxes and Bipartite Coverings.
Proceedings of the Mathematics of Paul Erdős II, 2013
2012
Theor. Comput. Sci., 2012
Nonnegative k-sums, fractional covers, and probability of small deviations.
J. Comb. Theory B, 2012
Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.
J. Comb. Theory A, 2012
Local correction of juntas.
Inf. Process. Lett., 2012
The Approximate Rank of a Matrix and its Algorithmic Applications.
Electron. Colloquium Comput. Complex., 2012
On Rigid Matrices and Subspace Polynomials.
Electron. Colloquium Comput. Complex., 2012
Dense uniform hypergraphs have high list chromatic number.
Discret. Math., 2012
A Non-linear Lower Bound for Planar Epsilon-nets.
Discret. Comput. Geom., 2012
The de Bruijn-Erdős theorem for hypergraphs.
Des. Codes Cryptogr., 2012
Optimizing budget allocation among channels and influencers.
Proceedings of the 21st World Wide Web Conference 2012, 2012
Nearly complete graphs decomposable into large induced matchings and their applications.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Space-efficient local computation algorithms.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Sequential voting with externalities: herding in social networks.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012
2011
Sparse Balanced Partitions and the Complexity of Subgraph Problems.
SIAM J. Discret. Math., 2011
Hypergraph list coloring and Euclidean Ramsey theory.
Random Struct. Algorithms, 2011
On graphs and algebraic graphs that do not contain cycles of length 4.
J. Graph Theory, 2011
The structure of almost all graphs in a hereditary property.
J. Comb. Theory B, 2011
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.
Electron. Colloquium Comput. Complex., 2011
Modular Orientations of Random and Quasi-Random Regular Graphs.
Comb. Probab. Comput., 2011
Many Random Walks Are Faster Than One.
Comb. Probab. Comput., 2011
Testing perfection is hard
CoRR, 2011
Local Correction of Boolean Functions
CoRR, 2011
On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game.
Electron. J. Comb., 2011
The Number of <i>f</i>-Matchings in Almost Every Tree is a Zero Residue.
Electron. J. Comb., 2011
Solving MAX-<i>r</i>-SAT Above a Tight Lower Bound.
Algorithmica, 2011
Sum of us: strategyproof selection from the selectors.
Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), 2011
Pragmatic Self-stabilization of Atomic Memory in Message-Passing Systems.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2011
Economical Graph Discovery.
Proceedings of the Innovations in Computer Science, 2011
List coloring and Euclidean Ramsey Theory.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011
2010
Typical peak sidelobe level of binary sequences.
IEEE Trans. Inf. Theory, 2010
Approximate Maximum Parsimony and Ancestral Maximum Likelihood.
IEEE ACM Trans. Comput. Biol. Bioinform., 2010
Balanced families of perfect hash functions and their applications.
ACM Trans. Algorithms, 2010
The Brunn--Minkowski Inequality and Nontrivial Cycles in the Discrete Torus.
SIAM J. Discret. Math., 2010
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
SIAM J. Comput., 2010
The inverse Banzhaf problem.
Soc. Choice Welf., 2010
Strategyproof Approximation of the Minimax on Networks.
Math. Oper. Res., 2010
A note on regular Ramsey graphs.
J. Graph Theory, 2010
A note on competitive diffusion through social networks.
Inf. Process. Lett., 2010
Practically Stabilizing Atomic Memory
CoRR, 2010
Another Abstraction of the Erdös-Szekeres Happy End Theorem.
Electron. J. Comb., 2010
Brief Announcement: Sharing Memory in a Self-stabilizing Manner.
Proceedings of the Distributed Computing, 24th International Symposium, 2010
Solving MAX-r-SAT Above a Tight Lower Bound.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
On Constant Time Approximation of Parameters of Bounded Degree Graphs.
Proceedings of the Property Testing - Current Research and Surveys, 2010
Solving Linear Systems through Nested Dissection.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
Proceedings of the COLT 2010, 2010
Testing Boolean Function Isomorphism.
Proceedings of the Approximation, 2010
2009
Optimal Monotone Encodings.
IEEE Trans. Inf. Theory, 2009
Hardness of edge-modification problems.
Theor. Comput. Sci., 2009
Admission control to minimize rejections and online set cover with repetitions.
ACM Trans. Algorithms, 2009
Can a Graph Have Distinct Regular Partitions?
SIAM J. Discret. Math., 2009
Spanning Directed Trees with Many Leaves.
SIAM J. Discret. Math., 2009
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.
SIAM J. Comput., 2009
The Online Set Cover Problem.
SIAM J. Comput., 2009
Induced subgraphs with distinct sizes.
Random Struct. Algorithms, 2009
Tell Me Who I Am: An Interactive Recommendation System.
Theory Comput. Syst., 2009
Stability-type results for hereditary properties.
J. Graph Theory, 2009
Playing to retain the advantage.
Electron. Notes Discret. Math., 2009
Balanced Hashing, Color Coding and Approximate Counting.
Electron. Colloquium Comput. Complex., 2009
Polychromatic Colorings of Plane Graphs.
Discret. Comput. Geom., 2009
Sizes of Induced Subgraphs of Ramsey Graphs.
Comb. Probab. Comput., 2009
Comb. Probab. Comput., 2009
Economical Elimination of Cycles in the Torus.
Comb. Probab. Comput., 2009
Perturbed Identity Matrices Have High Rank: Proof and Applications.
Comb. Probab. Comput., 2009
Strategyproof Approximation Mechanisms for Location on Networks
CoRR, 2009
Uniformly cross intersecting families.
Comb., 2009
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.
Algorithmica, 2009
On the power of two, three and four probes.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009
Choice-Memory Tradeoff in Allocations.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Trans. Algorithms, 2008
Cleaning Regular Graphs with Brushes.
SIAM J. Discret. Math., 2008
Large Nearly Regular Induced Subgraphs.
SIAM J. Discret. Math., 2008
Testing Triangle-Freeness in General Graphs.
SIAM J. Discret. Math., 2008
Every Monotone Graph Property Is Testable.
SIAM J. Comput., 2008
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.
SIAM J. Comput., 2008
What is the furthest graph from a hereditary property?
Random Struct. Algorithms, 2008
The maximum edit distance from hereditary graph properties.
J. Comb. Theory B, 2008
Weak ε-nets and interval chains.
J. ACM, 2008
Conflict-Free colorings of Shallow Discs.
Int. J. Comput. Geom. Appl., 2008
Deterministic Approximation Algorithms for the Nearest Codeword Problem.
Electron. Colloquium Comput. Complex., 2008
Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.
Electron. Colloquium Comput. Complex., 2008
An isoperimetric inequality in the universal cover of the punctured plane.
Discret. Math., 2008
Breaking the rhythm on graphs.
Discret. Math., 2008
Problems and results in extremal combinatorics - II.
Discret. Math., 2008
The Grothendieck constant of random and pseudo-random graphs.
Discret. Optim., 2008
The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence.
Electron. J. Comb., 2008
A separation theorem in property testing.
Comb., 2008
Optimal universal graphs with deterministic embedding.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Biomolecular network motif counting and discovery by color coding.
Proceedings of the Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), 2008
k-Wise Independent Random Graphs.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Broadcasting with Side Information.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
The complexity of the outer face in arrangements of random segments.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008
Small Sample Spaces Cannot Fool Low Degree Polynomials.
Proceedings of the Approximation, 2008
The Probabilistic Method, Third Edition.
Wiley-Interscience series in discrete mathematics and optimization, Wiley, ISBN: 978-0-470-17020-5, 2008
2007
Tracing Many Users With Almost No Rate Penalty.
IEEE Trans. Inf. Theory, 2007
Approximating the maximum clique minor and some subgraph homeomorphism problems.
Theor. Comput. Sci., 2007
Guessing secrets efficiently via list decoding.
ACM Trans. Algorithms, 2007
Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon.
SIAM J. Discret. Math., 2007
Turán's Theorem in the Hypercube.
SIAM J. Discret. Math., 2007
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.
SIAM J. Comput., 2007
On (epsilon, k)-min-wise independent permutations.
Random Struct. Algorithms, 2007
Sparse universal graphs for bounded-degree graphs.
Random Struct. Algorithms, 2007
On graphs with subgraphs having large independence numbers.
J. Graph Theory, 2007
Independent sets in tensor graph powers.
J. Graph Theory, 2007
Maximum directed cuts in acyclic digraphs.
J. Graph Theory, 2007
Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].
Inf. Comput., 2007
Hardness of fully dense problems.
Inf. Comput., 2007
Edge Colouring with Delays.
Comb. Probab. Comput., 2007
Privileged users in zero-error transmission over a noisy channel.
Comb., 2007
Codes And Xor Graph Products.
Comb., 2007
Embedding nearly-spanning bounded degree trees.
Comb., 2007
Testing k-wise and almost k-wise independence.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Improved approximation for directed cut problems.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Parameterized Algorithms for Directed Maximum Leaf Problems.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007
Better Algorithms and Bounds for Directed Maximum Leaf Problems.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007
Finding Disjoint Paths in Expanders Deterministically and Online.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.
Proceedings of the Algorithms, 2007
2006
The Shannon capacity of a graph and the independence numbers of its powers.
IEEE Trans. Inf. Theory, 2006
Algorithmic construction of sets for <i>k</i>-restrictions.
ACM Trans. Algorithms, 2006
A general approach to online network optimization problems.
ACM Trans. Algorithms, 2006
SIAM J. Discret. Math., 2006
Approximating the Cut-Norm via Grothendieck's Inequality.
SIAM J. Comput., 2006
Regular graphs whose subgraphs tend to be acyclic.
Random Struct. Algorithms, 2006
A Ramsey-type result for the hypercube.
J. Graph Theory, 2006
Dominating sets in k-majority tournaments.
J. Comb. Theory B, 2006
Multi-Node Graphs: A Framework for Multiplexed Biological Assays.
J. Comput. Biol., 2006
An Elementary Construction of Constant-Degree Expanders.
Electron. Colloquium Comput. Complex., 2006
A Characterization of Easily Testable Induced Subgraphs.
Comb. Probab. Comput., 2006
Measures of Pseudorandomness for Finite Sequences: Minimal Values.
Comb. Probab. Comput., 2006
Comb. Probab. Comput., 2006
Feasible Schedules for Rotating Transmissions.
Comb. Probab. Comput., 2006
H-Free Graphs of Large Minimum Degree.
Electron. J. Comb., 2006
The Number Of Orientations Having No Fixed Tournament.
Comb., 2006
On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.
Comb., 2006
Additive Approximation for Edge-Deletion Problems (Abstract).
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
2005
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing.
Theory Comput., 2005
Testing Reed-Muller codes.
IEEE Trans. Inf. Theory, 2005
Learning a Hidden Subgraph.
SIAM J. Discret. Math., 2005
Crossing patterns of semi-algebraic sets.
J. Comb. Theory A, 2005
On a Hypergraph Matching Problem.
Graphs Comb., 2005
Nonrepetitive colorings of graphs.
Electron. Notes Discret. Math., 2005
Partitioning multi-dimensional sets in a small number of "uniform" parts
Electron. Colloquium Comput. Complex., 2005
Homomorphisms in Graph Property Testing - A Survey
Electron. Colloquium Comput. Complex., 2005
Tight bounds for shared memory systems accessed by Byzantine processes.
Distributed Comput., 2005
Sharp Bounds For Some Multicolor Ramsey Numbers.
Comb., 2005
Quadratic forms on graphs.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Estimating arbitrary subset sums with few probes.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005
Additive Approximation for Edge-Deletion Problems.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
2004
Learning a Hidden Matching.
SIAM J. Comput., 2004
Dense graphs are antimagic.
J. Graph Theory, 2004
Testing subgraphs in directed graphs.
J. Comput. Syst. Sci., 2004
Algorithms with large domination ratio.
J. Algorithms, 2004
New Bounds on Parent-Identifying Codes: The Case of Multiple Parents.
Comb. Probab. Comput., 2004
Tight Estimates for Eigenvalues of Regular Graphs.
Electron. J. Comb., 2004
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices.
Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004
Edge Coloring with Delays.
Proceedings of the Approximation, 2004
2003
Typechecking XML views of relational databases.
ACM Trans. Comput. Log., 2003
Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.
Random Struct. Algorithms, 2003
Induced subgraphs of prescribed size.
J. Graph Theory, 2003
Partitioning into graphs with only small components.
J. Comb. Theory B, 2003
Generalized hashing and parent-identifying codes.
J. Comb. Theory A, 2003
Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory B, 2003
Random sampling and approximation of MAX-CSPs.
J. Comput. Syst. Sci., 2003
XML with data values: typechecking revisited.
J. Comput. Syst. Sci., 2003
Almost k-wise independence versus k-wise independence.
Inf. Process. Lett., 2003
A simple algorithm for edge-coloring bipartite multigraphs.
Inf. Process. Lett., 2003
Smaller Explicit Superconcentrators.
Internet Math., 2003
A Coding Theory Bound and Zero-Sum Square Matrices.
Graphs Comb., 2003
Factor <i>d</i>-domatic colorings of graphs.
Discret. Math., 2003
Problems and results in extremal combinatorics--I.
Discret. Math., 2003
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Comb. Probab. Comput., 2003
Testing Low-Degree Polynomials over GF(2(.
Proceedings of the Approximation, 2003
2002
SIAM J. Discret. Math., 2002
Nonrepetitive colorings of graphs.
Random Struct. Algorithms, 2002
On the discrepancy of combinatorial rectangles.
Random Struct. Algorithms, 2002
Testing subgraphs in large graphs.
Random Struct. Algorithms, 2002
A Ramsey-type problem and the Turán numbers.
J. Graph Theory, 2002
Tracking Join and Self-Join Sizes in Limited Storage.
J. Comput. Syst. Sci., 2002
Scalable Secure Storage When Half the System Is Faulty.
Inf. Comput., 2002
The Moore Bound for Irregular Graphs.
Graphs Comb., 2002
On partitions of discrete boxes.
Discret. Math., 2002
Covering a hypergraph of subgraphs.
Discret. Math., 2002
The Chromatic Number Of Graph Powers.
Comb. Probab. Comput., 2002
Algorithmic Aspects of Acyclic Edge Colorings.
Algorithmica, 2002
Transversal numbers for hypergraphs arising in geometry.
Adv. Appl. Math., 2002
Voting paradoxes and digraphs realizations.
Adv. Appl. Math., 2002
Explicit Unique-Neighbor Expanders.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms.
SIAM J. Discret. Math., 2001
Equireplicate Balanced Binary Codes for Oligo Arrays.
SIAM J. Discret. Math., 2001
On the maximum number of Hamiltonian paths in tournaments.
Random Struct. Algorithms, 2001
Acyclic edge colorings of graphs.
J. Graph Theory, 2001
Large induced forests in sparse graphs.
J. Graph Theory, 2001
Unextendible Product Bases.
J. Comb. Theory A, 2001
Parent-Identifying Codes.
J. Comb. Theory A, 2001
Linear Arboricity and Linear k-Arboricity of Regular Graphs.
Graphs Comb., 2001
Random Sampling and Approximation of MAX-CSP Problems
Electron. Colloquium Comput. Complex., 2001
On the Complexity of Arrangements of Circles in the Plane.
Discret. Comput. Geom., 2001
Recursive bounds for perfect hashing.
Discret. Appl. Math., 2001
Ramsey-type Theorems with Forbidden Subgraphs.
Comb., 2001
An optimal procedure for gap closing in whole genome shotgun sequencing.
Proceedings of the Fifth Annual International Conference on Computational Biology, 2001
Near-optimum Universal Graphs for Graphs with Bounded Degrees.
Proceedings of the Approximation, 2001
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
Lower Bounds for Approximations by Low Degree Polynomials Over Z<sub>m</sub>.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001
2000
Regular Languages are Testable with a Constant Number of Queries.
SIAM J. Comput., 2000
Degrees and choice numbers.
Random Struct. Algorithms, 2000
Long cycles in critical graphs.
J. Graph Theory, 2000
Decreasing the diameter of bounded degree graphs.
J. Graph Theory, 2000
On the Number of Permutations Avoiding a Given Pattern.
J. Comb. Theory A, 2000
On a Problem in Shuffling.
J. Comb. Theory A, 2000
Every<i>H</i>-decomposition of<i>K<sub>n</sub></i>has a Nearly Resolvable Alternative.
Eur. J. Comb., 2000
Triangle-free graphs with large chromatic numbers.
Discret. Math., 2000
Bipartite Subgraphs And The Smallest Eigenvalue.
Comb. Probab. Comput., 2000
String Quartets In Binary.
Comb. Probab. Comput., 2000
Locally Thin Set Families.
Comb. Probab. Comput., 2000
Comb. Probab. Comput., 2000
Efficient Testing of Large Graphs.
Comb., 2000
Universality and Tolerance.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000
The Probabilistic Method, Second Edition
John Wiley, ISBN: 978-0-47172215-1, 2000
1999
Short odd cycles in 4-chromatic graphs.
J. Graph Theory, 1999
Norm-Graphs: Variations and Applications.
J. Comb. Theory B, 1999
Non-averaging Subsets and Non-vanishing Transversals.
J. Comb. Theory A, 1999
Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory B, 1999
The Space Complexity of Approximating the Frequency Moments.
J. Comput. Syst. Sci., 1999
On Two Segmentation Problems.
J. Algorithms, 1999
Large Sets of Nearly Orthogonal Vectors.
Graphs Comb., 1999
Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.
Eur. J. Comb., 1999
Discret. Appl. Math., 1999
List Coloring of Random and Pseudo-Random Graphs.
Comb., 1999
Refining the Graph Density Condition for the Existence of Almost K-factors.
Ars Comb., 1999
Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths.
Proceedings of the Randomization, 1999
1998
Finding a large hidden clique in a random graph.
Random Struct. Algorithms, 1998
Approximating the independence number via the theta-function.
Math. Program., 1998
Progressions in Sequences of Nearly Consecutive Integers.
J. Comb. Theory A, 1998
On the Capacity of Digraphs.
Eur. J. Comb., 1998
Bipartite subgraphs of integer weighted graphs.
Discret. Math., 1998
Discret. Comput. Geom., 1998
T-choosability in Graphs.
Discret. Appl. Math., 1998
Perfect Matchings in ε-regular Graphs.
Electron. J. Comb., 1998
The Shannon Capacity of a Union.
Comb., 1998
On-Line and Off-Line Approximation Algorithms for Vector Covering Problems.
Algorithmica, 1998
Spectral Techniques in Graph Algorithms.
Proceedings of the LATIN '98: Theoretical Informatics, 1998
1997
A Spectral Technique for Coloring Random 3-Colorable Graphs.
SIAM J. Comput., 1997
Properly colored Hamilton cycles in edge-colored complete graphs.
Random Struct. Algorithms, 1997
Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs.
J. Comb. Theory A, 1997
A Note on Graph Colorings and Graph Polynomials.
J. Comb. Theory B, 1997
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph.
J. Comb. Theory A, 1997
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.
J. Comb. Theory B, 1997
On the Exponent of the All Pairs Shortest Path Problem.
J. Comput. Syst. Sci., 1997
Coins with Arbitrary Weights.
J. Algorithms, 1997
Scale-sensitive dimensions, uniform convergence, and learnability.
J. ACM, 1997
Constructive Bounds for a Ramsey-Type Problem.
Graphs Comb., 1997
Choosability and fractional chromatic numbers.
Discret. Math., 1997
Packings with large minimum kissing numbers.
Discret. Math., 1997
On the Edge-Expansion of Graphs.
Comb. Probab. Comput., 1997
Comb. Probab. Comput., 1997
Short Certificates for Tournaments.
Electron. J. Comb., 1997
A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture.
Electron. J. Comb., 1997
The Concentration of the Chromatic Number of Random Graphs.
Comb., 1997
Finding and Counting Given Length Cycles.
Algorithmica, 1997
Improved Parallel Approximation of a Class of Integer Programming Problems.
Algorithmica, 1997
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Approximation Schemes for Scheduling.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997
1996
Source coding and graph entropies.
IEEE Trans. Inf. Theory, 1996
A linear time erasure-resilient code with nearly optimal recovery.
IEEE Trans. Inf. Theory, 1996
Independence numbers of locally sparse graphs and a Ramsey type problem.
Random Struct. Algorithms, 1996
Approximate Hypergraph Coloring.
Nord. J. Comput., 1996
Edge-disjoint cycles in regular directed graphs.
J. Graph Theory, 1996
Vertex transversals that dominate.
J. Graph Theory, 1996
On <i>k</i>-saturated graphs with restrictions on the degrees.
J. Graph Theory, 1996
<i>H</i>-Factors in Dense Graphs.
J. Comb. Theory B, 1996
Disjoint Directed Cycles.
J. Comb. Theory, Ser. B, 1996
Matching Nuts and Bolts Faster.
Inf. Process. Lett., 1996
2-factors in dense graphs.
Discret. Math., 1996
Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.
Algorithmica, 1996
Derandomization Via Small Sample Spaces (Abstract).
Proceedings of the Algorithm Theory, 1996
Improved Parallel Approximation of a Class of Integer Programming Programming Problems.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996
The Geometry of Coin-Weighing Problems.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
On-line and Off-line Approximation Algorithms for Vector Covering Problems.
Proceedings of the Algorithms, 1996
1995
Repeated communication and Ramsey graphs.
IEEE Trans. Inf. Theory, 1995
A Graph-Theoretic Game and Its Application to the k-Server Problem.
SIAM J. Comput., 1995
The Acyclic Orientation Game on Random Graphs.
Random Struct. Algorithms, 1995
Random Struct. Algorithms, 1995
Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
Random Struct. Algorithms, 1995
The 123 Theorem and Its Extensions.
J. Comb. Theory A, 1995
epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.
Inf. Process. Lett., 1995
Long Non-Crossing Configurations in the Plane.
Fundam. Informaticae, 1995
Bounding the Piercing Number.
Discret. Comput. Geom., 1995
Covering with Latin Transversals.
Discret. Appl. Math., 1995
A Lattice Point Problem and Additive Number Theory.
Comb., 1995
Derandomized Graph Products.
Comput. Complex., 1995
Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.
Proceedings of the Algorithms, 1995
1994
A lower bound on the expected length of one-to-one codes.
IEEE Trans. Inf. Theory, 1994
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.
Theor. Comput. Sci., 1994
SIAM J. Discret. Math., 1994
Routing Permutations on Graphs Via Matchings.
SIAM J. Discret. Math., 1994
Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition.
SIAM J. Discret. Math., 1994
Random Cayley Graphs and Expanders.
Random Struct. Algorithms, 1994
Subdivided graphs have linear ramsey numbers.
J. Graph Theory, 1994
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).
J. Comput. Syst. Sci., 1994
The Algorithmic Aspects of the Regularity Lemma.
J. Algorithms, 1994
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time.
J. ACM, 1994
Packing of partial designs.
Graphs Comb., 1994
Electron. Colloquium Comput. Complex., 1994
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electron. Colloquium Comput. Complex., 1994
Probabilistic methods in coloring and decomposition problems.
Discret. Math., 1994
Can Visibility Graphs Be Represented Compactly?.
Discret. Comput. Geom., 1994
Perfect Hashing and Probability.
Comb. Probab. Comput., 1994
Explicit Ramsey graphs and orthonormal labelings.
Electron. J. Comb., 1994
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
A spectral technique for coloring random 3-colorable graphs (preliminary version).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
Finding and Counting Given Length Cycles (Extended Abstract).
Proceedings of the Algorithms, 1994
1993
Coin-Flipping Games Immune Against Linear-Sized Coalitions.
SIAM J. Comput., 1993
Addendum to "Simple Construction of Almost k-wise Independent Random Variables".
Random Struct. Algorithms, 1993
On three zero-sum Ramsey-type problems.
J. Graph Theory, 1993
Covering the Cube by Affine Hyperplanes.
Eur. J. Comb., 1993
Bisection of trees and sequences.
Discret. Math., 1993
On-Line Steine Trees in the Euclidean Plane.
Discret. Comput. Geom., 1993
Threshold Functions for H-factors.
Comb. Probab. Comput., 1993
Disjoint Systems (Extended Abstract).
Proceedings of the Algebraic Coding, 1993
1992
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.
IEEE Trans. Inf. Theory, 1992
Simple Construction of Almost k-wise Independent Random Variables.
Random Struct. Algorithms, 1992
The String Chromatic Number of a Graph.
Random Struct. Algorithms, 1992
Single Round Simulation on Radio Networks.
J. Algorithms, 1992
Almost<i>H</i>-factors in dense graphs.
Graphs Comb., 1992
Spanning subgraphs of random graphs.
Graphs Comb., 1992
Partitioning a rectangle into small perimeter rectangles.
Discret. Math., 1992
Transmitting in the <i>n</i>-Dimensional Cube.
Discret. Appl. Math., 1992
Point Selections and Weak e-Nets for Convex Hulls.
Comb. Probab. Comput., 1992
Choice Numbers of Graphs: a Probabilistic Approach.
Comb. Probab. Comput., 1992
Colorings and orientations of graphs.
Comb., 1992
Comparison-Sorting and Selecting in Totally Monotone Matrices.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Witnesses for Boolean Matrix Multiplication and for Shortest Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Random Cayley Graphs and Expanders (Abstract).
Proceedings of the Expanding Graphs, 1992
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992
On-Line Steiner Trees in the Euclidean Plane.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992
John Wiley, ISBN: 0-471-53588-5, 1992
1991
Acyclic Coloring of Graphs.
Random Struct. Algorithms, 1991
A Parallel Algorithmic Version of the Local Lemma.
Random Struct. Algorithms, 1991
Additive bases of vector spaces over prime fields.
J. Comb. Theory A, 1991
Multicolored forests in bipartite decompositions of graphs.
J. Comb. Theory B, 1991
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.
J. Comb. Theory A, 1991
A Lower Bound for Radio Broadcast.
J. Comput. Syst. Sci., 1991
Efficient Simulation of Finite Automata by Neural Nets.
J. ACM, 1991
Set systems with no union of cardinality 0 modulo<i>m</i>.
Graphs Comb., 1991
Ramsey graphs contain many distinct induced subgraphs.
Graphs Comb., 1991
On the second eigenvalue of a graph.
Discret. Math., 1991
Parallel comparison algorithms for approximation problems.
Comb., 1991
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract).
Proceedings of the On-Line Algorithms, 1991
1990
Linear Circuits over GF(2).
SIAM J. Comput., 1990
The Number of Spanning Trees in Regular Graphs.
Random Struct. Algorithms, 1990
Ramsey graphs cannot be defined by real polynomials.
J. Graph Theory, 1990
Generating Pseudo-Random Permutations and Maximum Flow Algorithms.
Inf. Process. Lett., 1990
Transversal numbers of uniform hypergraphs.
Graphs Comb., 1990
Not All Graphs are Segment T-graphs.
Eur. J. Comb., 1990
The CW-Inequalities for Vectors in l<sub>1</sub>.
Eur. J. Comb., 1990
Universal sequences for complete graphs.
Discret. Appl. Math., 1990
The maximum number of Hamiltonian paths in tournaments.
Comb., 1990
A Separator Theorem for Graphs with an Excluded Minor and its Applications
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Simple Constructions of Almost k-Wise Independent Random Variables
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
1989
On Neciporuk's Theorem for Branching Programs.
Theor. Comput. Sci., 1989
Finding an Approximate Maximum.
SIAM J. Comput., 1989
A counterexample to the rank-coloring conjecture.
J. Graph Theory, 1989
Cycles of length 0 modulo <i>k</i> in directed graphs.
J. Comb. Theory B, 1989
Combinatorial reconstruction problems.
J. Comb. Theory B, 1989
Legitimate colorings of projective planes.
Graphs Comb., 1989
Sub-Ramsey numbers for arithmetic progressions.
Graphs Comb., 1989
Graphs with a small number of distinct induced subgraphs.
Discret. Math., 1989
The star arboricity of graphs.
Discret. Math., 1989
The Maximum Size of a Convex Polygon in a Restricted Set in the Plane.
Discret. Comput. Geom., 1989
Cutting Disjoint Disks by Straight Lines.
Discret. Comput. Geom., 1989
Disjoint Edges in Geometric Graphs.
Discret. Comput. Geom., 1989
A nowhere-zero point in liner mappings.
Comb., 1989
Biased Coins and Randomized Algorithms.
Adv. Comput. Res., 1989
On the Complexity of Radio Communication (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
1988
Balancing sets of vectors.
IEEE Trans. Inf. Theory, 1988
Sorting, Approximate Sorting, and Searching in Rounds.
SIAM J. Discret. Math., 1988
The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms.
SIAM J. Comput., 1988
The average size of an independent set in graphs with a given chromatic number.
J. Comb. Theory B, 1988
Meanders and Their Applications in Lower Bounds Arguments.
J. Comput. Syst. Sci., 1988
Every 8-uniform 8-regular hypergraph is 2-colorable.
Graphs Comb., 1988
Explicit construction of linear sized tolerant networks.
Discret. Math., 1988
Sums of subsequences modulo prime powers.
Discret. Math., 1988
On sums of subsets of a set of integers.
Comb., 1988
1987
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.
J. Graph Theory, 1987
Better Expanders and Superconcentrators.
J. Algorithms, 1987
Large induced degenerate subgraphs.
Graphs Comb., 1987
On the kernel of intersecting families.
Graphs Comb., 1987
The smallets n-uniform hypergraph with positive discrepancy.
Comb., 1987
The monotone circuit complexity of Boolean functions.
Comb., 1987
On Disseminating Information Reliably without Broadcasting.
Proceedings of the 7th International Conference on Distributed Computing Systems, 1987
Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987
1986
The longest cycle of a graph with a large minimal degree.
J. Graph Theory, 1986
The number of small semispaces of a finite set of points in the plane.
J. Comb. Theory A, 1986
Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory.
J. Comb. Theory A, 1986
A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.
J. Algorithms, 1986
Decomposition of the complete<i>r</i>-graph into complete<i>r</i>-partite<i>r</i>-graphs.
Graphs Comb., 1986
Extremal Problems Concerning Transformations of the Set of Edges of the Complete Graph.
Eur. J. Comb., 1986
On the intersection of edges of a geometric graph by straight lines.
Discret. Math., 1986
Explicit construction of exponential sized families of k-independent sets.
Discret. Math., 1986
Covering a Square by Small Perimeter Rectangles.
Discret. Comput. Geom., 1986
Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory.
Comb., 1986
Covering graphs by the minimum number of equivalence relations.
Comb., 1986
Eigenvalues and expanders.
Comb., 1986
Meanders, Ramsey Theory and Lower Bounds for Branching Programs
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
Tight Complexity Bounds for Parallel Comparison Sorting
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
1985
lambda<sub>1</sub>, Isoperimetric inequalities for graphs, and superconcentrators.
J. Comb. Theory B, 1985
Even edge colorings of a graph.
J. Comb. Theory B, 1985
An Extremal Problem for Sets with Applications to Graph Theory.
J. Comb. Theory A, 1985
The maximum number of disjoint pairs in a family of subsets.
Graphs Comb., 1985
Hypergraphs with high chromatic number.
Graphs Comb., 1985
Asynchronous threshold networks.
Graphs Comb., 1985
A Simple Proof of the Upper Bound Theorem.
Eur. J. Comb., 1985
Separating Pairs of Points by Standard Boxes.
Eur. J. Comb., 1985
An Application of Graph Theory to Additive Number Theory.
Eur. J. Comb., 1985
Expanders, Sorting in Rounds and Superconcentrators of Limited Depth
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
Geometrical Realization of Set Systems and Probabilistic Communication Complexity
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Every 4-regular graph plus an edge contains a 3-regular subgraph.
J. Comb. Theory B, 1984
Regular subgraphs of almost regular graphs.
J. Comb. Theory B, 1984
A note on subdigraphs of digraphs with large outdegrees.
Discret. Math., 1984
Eigenvalues, Expanders and Superconcentrators (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
On a conjecture of erdöus, simonovits, and sós concerning anti-Ramsey theorems.
J. Graph Theory, 1983
On the density of sets of vectors.
Discret. Math., 1983
