Noga Alon

According to our database1, Noga Alon
  • authored at least 603 papers between 1983 and 2017.
  • has a "Dijkstra number"2 of three.

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

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

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.
CoRR, 2017

Testing hereditary properties of ordered graphs and matrices.
CoRR, 2017

Out-colourings of Digraphs.
CoRR, 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

Efficient Removal Lemmas for Matrices.
Proceedings of the Approximation, 2017

2016
Color Coding.
Encyclopedia of Algorithms, 2016

Linear Boolean Classification, Coding and the Critical Problem.
IEEE Trans. Information Theory, 2016

On the Maximum Quartet Distance between Phylogenetic Trees.
SIAM J. Discrete Math., 2016

Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes.
Journal of Graph Theory, 2016

Many T copies in H-free graphs.
J. Comb. Theory, Ser. B, 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.
Discrete Mathematics, 2016

On Active and Passive Testing.
Combinatorics, Probability & Computing, 2016

Dynamics of Evolving Social Groups.
CoRR, 2016

Duplication Distance to the Root for Binary Sequences.
CoRR, 2016

Removal Lemmas for Matrices.
CoRR, 2016

On the maximum quartet distance between phylogenetic trees.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Dynamics of Evolving Social Groups.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Reliable Communication over Highly Connected Noisy Networks.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 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. Discrete 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 and Combinatorics, 2015

Many T copies in H-free graphs.
Electronic Notes in Discrete Mathematics, 2015

Welfare Maximization with Limited Interaction.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Reliable Communication over Highly Connected Noisy Networks.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Easily Testable Graph Properties.
Combinatorics, Probability & Computing, 2015

On the maximum quartet distance between phylogenetic trees.
CoRR, 2015

Welfare Maximization with Limited Interaction.
CoRR, 2015

Corruption Detection on Networks.
CoRR, 2015

Online Learning with Feedback Graphs: Beyond Bandits.
CoRR, 2015

Drawing outerplanar graphs using three edge lengths.
Comput. Geom., 2015

Efficient Global Learning of Entailment Graphs.
Computational Linguistics, 2015

On Rigid Matrices and U-Polynomials.
Computational Complexity, 2015

Local Correction with Constant Error Rate.
Algorithmica, 2015

Redesigning the Israeli Medical Internship Match.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

How Robust Is the Wisdom of the Crowds?
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Welfare Maximization with Limited Interaction.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 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. Discrete Math., 2014

Correction: Basic Network Creation Games.
SIAM J. Discrete Math., 2014

Maximizing the Number of Nonnegative Subsets.
SIAM J. Discrete 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.
Discrete Applied Mathematics, 2014

Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback.
CoRR, 2014

Separation dimension of bounded degree graphs.
CoRR, 2014

Linear Boolean classification, coding and "the critical problem".
CoRR, 2014

On the compatibility of quartet trees.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 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 of Computing, 2013

Adversarial Leakage in Games.
SIAM J. Discrete Math., 2013

Basic Network Creation Games.
SIAM J. Discrete Math., 2013

Minimizing the Number of Carries in Addition.
SIAM J. Discrete 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

The chromatic number of random Cayley graphs.
Eur. J. Comb., 2013

Beeping a maximal independent set.
Distributed Computing, 2013

On active and passive testing.
CoRR, 2013

From Bandits to Experts: A Tale of Domination and Independence.
CoRR, 2013

On sunflowers and matrix multiplication.
Computational Complexity, 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 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

On Rigid Matrices and U-polynomials.
Proceedings of the 28th Conference on Computational Complexity, 2013

How to Put through Your Agenda in Collective Binary Decisions.
Proceedings of the Algorithmic Decision Theory - Third International Conference, 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.
Discrete Mathematics, 2012

A Non-linear Lower Bound for Planar Epsilon-nets.
Discrete & Computational Geometry, 2012

The de Bruijn-Erdős theorem for hypergraphs.
Des. Codes Cryptography, 2012

Local Correction with Constant Error Rate
CoRR, 2012

Beeping a Maximal Independent Set
CoRR, 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 ACM Conference on Electronic Commerce, 2012

On Sunflowers and Matrix Multiplication.
Proceedings of the 27th Conference on Computational Complexity, 2012

Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Sparse Balanced Partitions and the Complexity of Subgraph Problems.
SIAM J. Discrete 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

On Sunflowers and Matrix Multiplication.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Modular Orientations of Random and Quasi-Random Regular Graphs.
Combinatorics, Probability & Computing, 2011

Many Random Walks Are Faster Than One.
Combinatorics, Probability & Computing, 2011

Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
CoRR, 2011

Testing perfection is hard
CoRR, 2011

Space-efficient Local Computation Algorithms
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

Beeping a Maximal Independent Set.
Proceedings of the Distributed Computing - 25th International Symposium, 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. Information 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. Discrete 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.
Discrete Mathematics, 2010

Playing to Retain the Advantage.
Combinatorics, Probability & Computing, 2010

Introduction.
Combinatorics, Probability & Computing, 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

Basic network creation games.
Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 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, 2010

Bayesian ignorance.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Adversarial Leakage in Games.
Proceedings of the Innovations in Computer Science, 2010

Solving Linear Systems through Nested Dissection.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

A Non-linear Lower Bound for Planar Epsilon-Nets.
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. Information 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. Discrete Math., 2009

Spanning Directed Trees with Many Leaves.
SIAM J. Discrete 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.
Electronic Notes in Discrete Mathematics, 2009

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

Polychromatic Colorings of Plane Graphs.
Discrete & Computational Geometry, 2009

Sizes of Induced Subgraphs of Ramsey Graphs.
Combinatorics, Probability & Computing, 2009

Introduction.
Combinatorics, Probability & Computing, 2009

Economical Elimination of Cycles in the Torus.
Combinatorics, Probability & Computing, 2009

Perturbed Identity Matrices Have High Rank: Proof and Applications.
Combinatorics, Probability & Computing, 2009

Sum of Us: Strategyproof Selection from the Selectors
CoRR, 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

Balanced Hashing, Color Coding and Approximate Counting.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 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

Deterministic approximation algorithms for the nearest codeword problem.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Deterministic Approximation Algorithms for the Nearest Codeword Problem.
Proceedings of the Approximation, 2009

2008
Color Coding.
Proceedings of the Encyclopedia of Algorithms, 2008

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Trans. Algorithms, 2008

Cleaning Regular Graphs with Brushes.
SIAM J. Discrete Math., 2008

Large Nearly Regular Induced Subgraphs.
SIAM J. Discrete Math., 2008

Testing Triangle-Freeness in General Graphs.
SIAM J. Discrete 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. Geometry 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.
Discrete Mathematics, 2008

Breaking the rhythm on graphs.
Discrete Mathematics, 2008

Problems and results in extremal combinatorics - II.
Discrete Mathematics, 2008

The Grothendieck constant of random and pseudo-random graphs.
Discrete Optimization, 2008

An Elementary Construction of Constant-Degree Expanders.
Combinatorics, Probability & Computing, 2008

A note on regular Ramsey graphs
CoRR, 2008

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
CoRR, 2008

Broadcasting with side information
CoRR, 2008

Balanced Families of Perfect Hash Functions and Their Applications
CoRR, 2008

Admission Control to Minimize Rejections and Online Set Cover with Repetitions
CoRR, 2008

Spanning directed trees with many leaves
CoRR, 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

Many random walks are faster than one.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 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

Optimal Monotone Encodings.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 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

Polychromatic colorings of plane graphs.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Small Sample Spaces Cannot Fool Low Degree Polynomials.
Proceedings of the Approximation, 2008

2007
Tracing Many Users With Almost No Rate Penalty.
IEEE Trans. Information 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. Discrete Math., 2007

Tur[a-acute]n's Theorem in the Hypercube.
SIAM J. Discrete 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.
Combinatorics, Probability & Computing, 2007

Parameterized Algorithms for Directed Maximum Leaf Problems
CoRR, 2007

Better Algorithms and Bounds for Directed Maximum Leaf Problems
CoRR, 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

An elementary construction of constant-degree expanders.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Balanced Families of Perfect Hash Functions and Their Applications.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Parameterized Algorithms for Directed Maximum Leaf Problems.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
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

Can a Graph Have Distinct Regular Partitions?
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
The Shannon capacity of a graph and the independence numbers of its powers.
IEEE Trans. Information 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. Discrete 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.
Journal of Computational Biology, 2006

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

An Elementary Construction of Constant-Degree Expanders.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Explicit construction of linear sized tolerant networks.
Discrete Mathematics, 2006

A Characterization of Easily Testable Induced Subgraphs.
Combinatorics, Probability & Computing, 2006

Measures of Pseudorandomness for Finite Sequences: Minimal Values.
Combinatorics, Probability & Computing, 2006

Splitting digraphs.
Combinatorics, Probability & Computing, 2006

Feasible Schedules for Rotating Transmissions.
Combinatorics, Probability & Computing, 2006

The Shannon capacity of a graph and the independence numbers of its powers
CoRR, 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

A combinatorial characterization of the testable graph properties: it's all about regularity.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Tell me who I am: an interactive recommendation system.
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Testing triangle-freeness in general graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Additive Approximation for Edge-Deletion Problems (Abstract).
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Conflict-free colorings of shallow discs.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing.
Theory of Computing, 2005

Testing Reed-Muller codes.
IEEE Trans. Information Theory, 2005

Learning a Hidden Subgraph.
SIAM J. Discrete Math., 2005

Crossing patterns of semi-algebraic sets.
J. Comb. Theory, Ser. A, 2005

On a Hypergraph Matching Problem.
Graphs and Combinatorics, 2005

Nonrepetitive colorings of graphs.
Electronic Notes in Discrete Mathematics, 2005

Partitioning multi-dimensional sets in a small number of "uniform" parts
Electronic Colloquium on Computational Complexity (ECCC), 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 Computing, 2005

Discrepancy Games.
Electr. J. Comb., 2005

Sharp Bounds For Some Multicolor Ramsey Numbers.
Combinatorica, 2005

Every monotone graph property is testable.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quadratic forms on graphs.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Admission control to minimize rejections and online set cover with repetitions.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Linear equations, arithmetic progressions and hypergraph property testing.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

A Characterization of the (natural) Graph Properties Testable with One-Sided Error.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Testing of Clustering.
SIAM Review, 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.
Combinatorics, Probability & Computing, 2004

Tight Estimates for Eigenvalues of Regular Graphs.
Electr. J. Comb., 2004

Approximating the cut-norm via Grothendieck's inequality.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

A characterization of easily testable induced subgraphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A general approach to online network optimization problems.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Learning a Hidden Subgraph.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 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. Discrete 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 Mathematics, 2003

A Coding Theory Bound and Zero-Sum Square Matrices.
Graphs and Combinatorics, 2003

Factor d-domatic colorings of graphs.
Discrete Mathematics, 2003

Problems and results in extremal combinatorics--I.
Discrete Mathematics, 2003

Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Combinatorics, Probability & Computing, 2003

Testing subgraphs in directed graphs.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The online set cover problem.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Smaller explicit superconcentrators.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Testing Low-Degree Polynomials over GF(2(.
Proceedings of the Approximation, 2003

2002
Testing k-colorability.
SIAM J. Discrete 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 and Combinatorics, 2002

Almost k-wise independence versus k-wise independence.
Electronic Colloquium on Computational Complexity (ECCC), 2002

On partitions of discrete boxes.
Discrete Mathematics, 2002

Game domination number.
Discrete Mathematics, 2002

Covering a hypergraph of subgraphs.
Discrete Mathematics, 2002

The Chromatic Number Of Graph Powers.
Combinatorics, Probability & Computing, 2002

Algorithmic Aspects of Acyclic Edge Colorings.
Algorithmica, 2002

Random sampling and approximation of MAX-CSP problems.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Testing satisfiability.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Guessing secrets efficiently via list decoding.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Explicit Unique-Neighbor Expanders.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Learning a Hidden Matching.
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. Discrete Math., 2001

Equireplicate Balanced Binary Codes for Oligo Arrays.
SIAM J. Discrete 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 and Combinatorics, 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.
Discrete & Computational Geometry, 2001

Recursive bounds for perfect hashing.
Discrete Applied Mathematics, 2001

Ramsey-type Theorems with Forbidden Subgraphs.
Combinatorica, 2001

Constructing worst case instances for semidefinite programming based approximation algorithms.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 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

XML with Data Values: Typechecking Revisited.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Typechecking XML Views of Relational Databases.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 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

Testing Subgraphs in Large Graphs.
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.
Discrete Mathematics, 2000

Bipartite Subgraphs And The Smallest Eigenvalue.
Combinatorics, Probability & Computing, 2000

String Quartets In Binary.
Combinatorics, Probability & Computing, 2000

Locally Thin Set Families.
Combinatorics, Probability & Computing, 2000

Packing Ferrers Shapes.
Combinatorics, Probability & Computing, 2000

Efficient Testing of Large Graphs.
Combinatorica, 2000

Scalable Secure Storage when Half the System Is Faulty.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Testing of Clustering.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Universality and Tolerance.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 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 and Combinatorics, 1999

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

Separable Partitions.
Discrete Applied Mathematics, 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

Tracking Join and Self-Join Sizes in Limited Storage.
Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31, 1999

Regular Languages Are Testable with a Constant Number of Queries.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Efficient Testing of Large Graphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 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.
Discrete Mathematics, 1998

Piercing d -Intervals.
Discrete & Computational Geometry, 1998

T-choosability in Graphs.
Discrete Applied Mathematics, 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

Finding a Large Hidden Clique in a Random Graph.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 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 and Combinatorics, 1997

Choosability and fractional chromatic numbers.
Discrete Mathematics, 1997

Packings with large minimum kissing numbers.
Discrete Mathematics, 1997

On the Edge-Expansion of Graphs.
Combinatorics, Probability & Computing, 1997

Intersecting Systems.
Combinatorics, Probability & Computing, 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. Information Theory, 1996

A linear time erasure-resilient code with nearly optimal recovery.
IEEE Trans. Information 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.
Discrete Mathematics, 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

The Space Complexity of Approximating the Frequency Moments.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 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. Information 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.
Discrete & Computational Geometry, 1995

Covering with Latin Transversals.
Discrete Applied Mathematics, 1995

A Lattice Point Problem and Additive Number Theory.
Combinatorica, 1995

Derandomized Graph Products.
Computational Complexity, 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. Information Theory, 1994

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.
Theor. Comput. Sci., 1994

Planar Separators.
SIAM J. Discrete Math., 1994

Routing Permutations on Graphs Via Matchings.
SIAM J. Discrete Math., 1994

Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition.
SIAM J. Discrete 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 and Combinatorics, 1994

Color-Coding
Electronic Colloquium on Computational Complexity (ECCC), 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.
Discrete Mathematics, 1994

Can Visibility Graphs Be Represented Compactly?.
Discrete & Computational Geometry, 1994

Perfect Hashing and Probability.
Combinatorics, Probability & Computing, 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.
Discrete Mathematics, 1993

On-Line Steine Trees in the Euclidean Plane.
Discrete & Computational Geometry, 1993

Threshold Functions for H-factors.
Combinatorics, Probability & Computing, 1993

Routing permutations on graphs via matchings.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Scale-sensitive Dimensions, Uniform Convergence, and Learnability
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Disjoint Systems (Extended Abstract).
Proceedings of the Algebraic Coding, 1993

Long Non-Crossing Configurations in the Plane.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Can Visibility Graphs be Represented Compactly?
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

1992
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.
IEEE Trans. Information 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 and Combinatorics, 1992

Generalized sum graphs.
Graphs and Combinatorics, 1992

Spanning subgraphs of random graphs.
Graphs and Combinatorics, 1992

Partitioning a rectangle into small perimeter rectangles.
Discrete Mathematics, 1992

Transmitting in the n-Dimensional Cube.
Discrete Applied Mathematics, 1992

Point Selections and Weak e-Nets for Convex Hulls.
Combinatorics, Probability & Computing, 1992

Choice Numbers of Graphs: a Probabilistic Approach.
Combinatorics, Probability & Computing, 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 and Combinatorics, 1991

Ramsey graphs contain many distinct induced subgraphs.
Graphs and Combinatorics, 1991

On the second eigenvalue of a graph.
Discrete Mathematics, 1991

Parallel comparison algorithms for approximation problems.
Combinatorica, 1991

On the Exponent of the All Pairs Shortest Path Problem
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

A parallel algorithmic version of the Local Lemma
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 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 and Combinatorics, 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.
Discrete Applied Mathematics, 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

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time
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 and Combinatorics, 1989

Sub-Ramsey numbers for arithmetic progressions.
Graphs and Combinatorics, 1989

Graphs with a small number of distinct induced subgraphs.
Discrete Mathematics, 1989

The star arboricity of graphs.
Discrete Mathematics, 1989

The Maximum Size of a Convex Polygon in a Restricted Set in the Plane.
Discrete & Computational Geometry, 1989

Cutting Disjoint Disks by Straight Lines.
Discrete & Computational Geometry, 1989

Disjoint Edges in Geometric Graphs.
Discrete & Computational Geometry, 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. Information Theory, 1988

Sorting, Approximate Sorting, and Searching in Rounds.
SIAM J. Discrete 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 and Combinatorics, 1988

Explicit construction of linear sized tolerant networks.
Discrete Mathematics, 1988

Sums of subsequences modulo prime powers.
Discrete Mathematics, 1988

On sums of subsets of a set of integers.
Combinatorica, 1988

Parallel Comparison Algorithms for Approximation Problems
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.
Journal of Graph Theory, 1987

Better Expanders and Superconcentrators.
J. Algorithms, 1987

Large induced degenerate subgraphs.
Graphs and Combinatorics, 1987

On the kernel of intersecting families.
Graphs and Combinatorics, 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

The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 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 and Combinatorics, 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.
Discrete Mathematics, 1986

Explicit construction of exponential sized families of k-independent sets.
Discrete Mathematics, 1986

Covering a Square by Small Perimeter Rectangles.
Discrete & Computational Geometry, 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 and Combinatorics, 1985

Hypergraphs with high chromatic number.
Graphs and Combinatorics, 1985

Asynchronous threshold networks.
Graphs and Combinatorics, 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.
Discrete Mathematics, 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.
Discrete Mathematics, 1983


  Loading...