Noga Alon

According to our database1, Noga Alon authored at least 540 papers between 1983 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Awards

ACM Fellow

ACM Fellow 2016, "For contributions in the study of expander graphs, derandomization and streaming algorithms".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Multitasking Capacity: Hardness Results and Improved Constructions.
SIAM J. Discret. Math., 2020

Efficient Removal Lemmas for Matrices.
Order, 2020

Out-colourings of digraphs.
Journal of Graph Theory, 2020

On the product dimension of clique factors.
Eur. J. Comb., 2020

Edge-statistics on large graphs.
Comb. Probab. Comput., 2020

Efficient Splitting of Measures and Necklaces.
CoRR, 2020

Palette Sparsification Beyond (Δ+1) Vertex Coloring.
CoRR, 2020

Hierarchical Clustering: a 0.585 Revenue Approximation.
CoRR, 2020

Explicit expanders of every degree and size.
CoRR, 2020

Closure Properties for Private Classification and Online Prediction.
CoRR, 2020

Boosting Simple Learners.
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.
Combinatorica, 2020

The ε-t-Net Problem.
Proceedings of the 36th International Symposium on Computational Geometry, 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

Traces of hypergraphs.
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

The Hat Guessing Number of Graphs.
Proceedings of the IEEE International Symposium on Information Theory, 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.
Journal of 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

The Price of Bounded Preemption.
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 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.
Journal of Graph Theory, 2017

Testing hereditary properties of ordered graphs and matrices.
Electronic Colloquium on Computational Complexity (ECCC), 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
Color Coding.
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.
Journal of Graph Theory, 2016

High girth augmented trees are huge.
J. Comb. Theory, Ser. A, 2016

Testing Equality in Communication Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Journal of Graph Theory, 2015

Comparable pairs in families of sets.
J. Comb. Theory, Ser. B, 2015

Bipartite decomposition of random graphs.
J. Comb. Theory, Ser. 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

Many T copies in H-free graphs.
Electron. Notes Discret. Math., 2015

Welfare Maximization with Limited Interaction.
Electronic Colloquium on Computational Complexity (ECCC), 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, Ser. A, 2014

Sign rank, VC dimension and spectral gaps.
Electronic Colloquium on Computational Complexity (ECCC), 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
Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions.
Theory Comput., 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.
Journal of Graph Theory, 2013

The Turán number of sparse spanning graphs.
J. Comb. Theory, Ser. 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
Bayesian ignorance.
Theor. Comput. Sci., 2012

Nonnegative k-sums, fractional covers, and probability of small deviations.
J. Comb. Theory, Ser. B, 2012

Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.
J. Comb. Theory, Ser. A, 2012

Local correction of juntas.
Inf. Process. Lett., 2012

The Approximate Rank of a Matrix and its Algorithmic Applications.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On Rigid Matrices and Subspace Polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Journal of Graph Theory, 2011

The structure of almost all graphs in a hereditary property.
J. Comb. Theory, Ser. B, 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

MIS on the fly
CoRR, 2011

On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game.
Electr. J. Comb., 2011

The Number of f-Matchings in Almost Every Tree is a Zero Residue.
Electr. J. Comb., 2011

Solving MAX-r-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. Biology 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.
Social Choice and Welfare, 2010

Strategyproof Approximation of the Minimax on Networks.
Math. Oper. Res., 2010

A note on regular Ramsey graphs.
Journal of Graph Theory, 2010

A note on competitive diffusion through social networks.
Inf. Process. Lett., 2010

Walking in circles.
Discret. Math., 2010

Practically Stabilizing Atomic Memory
CoRR, 2010

Another Abstraction of the Erdös-Szekeres Happy End Theorem.
Electr. 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

Voting Paradoxes.
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.
Journal of Graph Theory, 2009

Playing to retain the advantage.
Electron. Notes Discret. Math., 2009

Balanced Hashing, Color Coding and Approximate Counting.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Polychromatic Colorings of Plane Graphs.
Discret. Comput. Geom., 2009

Sizes of Induced Subgraphs of Ramsey Graphs.
Comb. Probab. Comput., 2009

Introduction.
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.
Combinatorica, 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

Fast FAST.
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
Color Coding.
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, Ser. 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.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.
Electronic Colloquium on Computational Complexity (ECCC), 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

An Elementary Construction of Constant-Degree Expanders.
Comb. Probab. Comput., 2008

The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence.
Electr. J. Comb., 2008

A separation theorem in property testing.
Combinatorica, 2008

Weak ε-nets and interval chains.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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[a-acute]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.
Journal of Graph Theory, 2007

Independent sets in tensor graph powers.
Journal of Graph Theory, 2007

Maximum directed cuts in acyclic digraphs.
Journal of 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

Partitioning multi-dimensional sets in a small number of "uniform" parts.
Eur. J. Comb., 2007

Edge Colouring with Delays.
Comb. Probab. Comput., 2007

Privileged users in zero-error transmission over a noisy channel.
Combinatorica, 2007

Codes And Xor Graph Products.
Combinatorica, 2007

Embedding nearly-spanning bounded degree trees.
Combinatorica, 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 k-restrictions.
ACM Trans. Algorithms, 2006

A general approach to online network optimization problems.
ACM Trans. Algorithms, 2006

Ranking Tournaments.
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.
Journal of Graph Theory, 2006

Dominating sets in k-majority tournaments.
J. Comb. Theory, Ser. B, 2006

Multi-Node Graphs: A Framework for Multiplexed Biological Assays.
J. Comput. Biol., 2006

Tracing a single user.
Eur. J. Comb., 2006

A Characterization of Easily Testable Induced Subgraphs.
Comb. Probab. Comput., 2006

Measures of Pseudorandomness for Finite Sequences: Minimal Values.
Comb. Probab. Comput., 2006

Splitting digraphs.
Comb. Probab. Comput., 2006

Feasible Schedules for Rotating Transmissions.
Comb. Probab. Comput., 2006

H-Free Graphs of Large Minimum Degree.
Electr. J. Comb., 2006

The Number Of Orientations Having No Fixed Tournament.
Combinatorica, 2006

On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.
Combinatorica, 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, Ser. A, 2005

On a Hypergraph Matching Problem.
Graphs Comb., 2005

Nonrepetitive colorings of graphs.
Electron. Notes Discret. Math., 2005

Homomorphisms in Graph Property Testing - A Survey
Electronic Colloquium on Computational Complexity (ECCC), 2005

Tight bounds for shared memory systems accessed by Byzantine processes.
Distributed Comput., 2005

Discrepancy Games.
Electr. J. Comb., 2005

Sharp Bounds For Some Multicolor Ramsey Numbers.
Combinatorica, 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.
Journal of 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.
Electr. 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

Testing of Clustering.
SIAM J. Discret. Math., 2003

Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.
Random Struct. Algorithms, 2003

Induced subgraphs of prescribed size.
Journal of Graph Theory, 2003

Partitioning into graphs with only small components.
J. Comb. Theory, Ser. B, 2003

Generalized hashing and parent-identifying codes.
J. Comb. Theory, Ser. A, 2003

Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory, Ser. 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

Testing satisfiability.
J. Algorithms, 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 d-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
Testing k-colorability.
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.
Journal of 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

Game domination number.
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.
Journal of Graph Theory, 2001

Large induced forests in sparse graphs.
Journal of Graph Theory, 2001

Unextendible Product Bases.
J. Comb. Theory, Ser. A, 2001

Parent-Identifying Codes.
J. Comb. Theory, Ser. A, 2001

Linear Arboricity and Linear k-Arboricity of Regular Graphs.
Graphs Comb., 2001

Random Sampling and Approximation of MAX-CSP Problems
Electronic Colloquium on Computational Complexity (ECCC), 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.
Combinatorica, 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 Zm.
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.
Journal of Graph Theory, 2000

Decreasing the diameter of bounded degree graphs.
Journal of Graph Theory, 2000

On the Number of Permutations Avoiding a Given Pattern.
J. Comb. Theory, Ser. A, 2000

On a Problem in Shuffling.
J. Comb. Theory, Ser. A, 2000

EveryH-decomposition ofKnhas 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

Packing Ferrers Shapes.
Comb. Probab. Comput., 2000

Efficient Testing of Large Graphs.
Combinatorica, 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.
Journal of Graph Theory, 1999

Norm-Graphs: Variations and Applications.
J. Comb. Theory, Ser. B, 1999

Non-averaging Subsets and Non-vanishing Transversals.
J. Comb. Theory, Ser. A, 1999

Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory, Ser. B, 1999

The Space Complexity of Approximating the Frequency Moments.
J. Comput. Syst. Sci., 1999

On Two Segmentation Problems.
J. Algorithms, 1999

Linear Hash Functions.
J. ACM, 1999

Large Sets of Nearly Orthogonal Vectors.
Graphs Comb., 1999

Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.
Eur. J. Comb., 1999

Separable Partitions.
Discret. Appl. Math., 1999

List Coloring of Random and Pseudo-Random Graphs.
Combinatorica, 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, Ser. A, 1998

On the Capacity of Digraphs.
Eur. J. Comb., 1998

Bipartite subgraphs of integer weighted graphs.
Discret. Math., 1998

Piercing d -Intervals.
Discret. Comput. Geom., 1998

T-choosability in Graphs.
Discret. Appl. Math., 1998

Perfect Matchings in ε-regular Graphs.
Electr. J. Comb., 1998

The Shannon Capacity of a Union.
Combinatorica, 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, Ser. A, 1997

A Note on Graph Colorings and Graph Polynomials.
J. Comb. Theory, Ser. B, 1997

On the Degree, Size, and Chromatic Index of a Uniform Hypergraph.
J. Comb. Theory, Ser. A, 1997

Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.
J. Comb. Theory, Ser. 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

Intersecting Systems.
Comb. Probab. Comput., 1997

Short Certificates for Tournaments.
Electr. J. Comb., 1997

A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture.
Electr. J. Comb., 1997

The Concentration of the Chromatic Number of Random Graphs.
Combinatorica, 1997

Finding and Counting Given Length Cycles.
Algorithmica, 1997

Improved Parallel Approximation of a Class of Integer Programming Problems.
Algorithmica, 1997

Is Linear Hashing Good?
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.
Journal of Graph Theory, 1996

Vertex transversals that dominate.
Journal of Graph Theory, 1996

On k-saturated graphs with restrictions on the degrees.
Journal of Graph Theory, 1996

H-Factors in Dense Graphs.
J. Comb. Theory, Ser. 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

Bipartite Subgraphs.
Combinatorica, 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

Disjoint Systems.
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, Ser. A, 1995

Color-Coding.
J. ACM, 1995

epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.
Inf. Process. Lett., 1995

Long Non-Crossing Configurations in the Plane.
Fundam. Inform., 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.
Combinatorica, 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

Planar Separators.
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.
Journal of 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

Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electr. 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

Matching Nuts and Bolts.
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.
Journal of 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

AlmostH-factors in dense graphs.
Graphs Comb., 1992

Generalized sum 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 n-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.
Combinatorica, 1992

Star arboricity.
Combinatorica, 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

Piercing Convex Sets.
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

The Probabilistic Method
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, Ser. A, 1991

Multicolored forests in bipartite decompositions of graphs.
J. Comb. Theory, Ser. B, 1991

Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.
J. Comb. Theory, Ser. 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 modulom.
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.
Combinatorica, 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.
Journal of 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 l1.
Eur. J. Comb., 1990

Universal sequences for complete graphs.
Discret. Appl. Math., 1990

The maximum number of Hamiltonian paths in tournaments.
Combinatorica, 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.
Journal of Graph Theory, 1989

Ascending waves.
J. Comb. Theory, Ser. A, 1989

Cycles of length 0 modulo k in directed graphs.
J. Comb. Theory, Ser. B, 1989

Combinatorial reconstruction problems.
J. Comb. Theory, Ser. 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.
Combinatorica, 1989

Biased Coins and Randomized Algorithms.
Advances in Computing Research, 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, Ser. 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.
Combinatorica, 1988

1987
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.
Journal of 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.
Combinatorica, 1987

The monotone circuit complexity of Boolean functions.
Combinatorica, 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.
Journal of Graph Theory, 1986

The number of small semispaces of a finite set of points in the plane.
J. Comb. Theory, Ser. A, 1986

Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory.
J. Comb. Theory, Ser. A, 1986

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.
J. Algorithms, 1986

Decomposition of the completer-graph into completer-partiter-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.
Combinatorica, 1986

Covering graphs by the minimum number of equivalence relations.
Combinatorica, 1986

Eigenvalues and expanders.
Combinatorica, 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
lambda1, Isoperimetric inequalities for graphs, and superconcentrators.
J. Comb. Theory, Ser. B, 1985

Even edge colorings of a graph.
J. Comb. Theory, Ser. B, 1985

An Extremal Problem for Sets with Applications to Graph Theory.
J. Comb. Theory, Ser. 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, Ser. B, 1984

Regular subgraphs of almost regular graphs.
J. Comb. Theory, Ser. 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.
Journal of Graph Theory, 1983

On the density of sets of vectors.
Discret. Math., 1983


  Loading...