Noga Alon

Gil Cohen

Proceedings of the 28th Conference on Computational Complexity, 2013

How to Put through Your Agenda in Collective Binary Decisions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Decision Theory - Third International Conference, 2013

The Value of Ignorance about the Number of Players.

[BibT_eX]

[DOI]

Reshef Meir

Moshe Tennenholtz

Proceedings of the Late-Breaking Developments in the Field of Artificial Intelligence, 2013

Bundling Attacks in Judgment Aggregation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

Neighborly Families of Boxes and Bipartite Coverings.

[BibT_eX]

[DOI]

Proceedings of the Mathematics of Paul Erdős II, 2013

2012

Nonnegative k-sums, fractional covers, and probability of small deviations.

[BibT_eX]

[DOI]

Hao Huang

J. Comb. Theory B, 2012

Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2012

Local correction of juntas.

[BibT_eX]

[DOI]

Amit Weinstein

Inf. Process. Lett., 2012

The Approximate Rank of a Matrix and its Algorithmic Applications.

[BibT_eX]

[DOI]

Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2012

On Rigid Matrices and Subspace Polynomials.

[BibT_eX]

[DOI]

Gil Cohen

Electron. Colloquium Comput. Complex., 2012

Dense uniform hypergraphs have high list chromatic number.

[BibT_eX]

[DOI]

Discret. Math., 2012

The de Bruijn-Erdős theorem for hypergraphs.

[BibT_eX]

[DOI]

Des. Codes Cryptogr., 2012

Optimizing budget allocation among channels and influencers.

[BibT_eX]

[DOI]

Iftah Gamzu

Moshe Tennenholtz

Proceedings of the 21st World Wide Web Conference 2012, 2012

Nearly complete graphs decomposable into large induced matchings and their applications.

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Space-efficient local computation algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Sequential voting with externalities: herding in social networks.

[BibT_eX]

[DOI]

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

On Sunflowers and Matrix Multiplication.

[BibT_eX]

[DOI]

Amir Shpilka

Christopher Umans

Proceedings of the 27th Conference on Computational Complexity, 2012

Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions.

[BibT_eX]

[DOI]

Shachar Lovett

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Sparse Balanced Partitions and the Complexity of Subgraph Problems.

[BibT_eX]

[DOI]

Dániel Marx

SIAM J. Discret. Math., 2011

Hypergraph list coloring and Euclidean Ramsey theory.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2011

On graphs and algebraic graphs that do not contain cycles of length 4.

[BibT_eX]

[DOI]

J. Graph Theory, 2011

The structure of almost all graphs in a hereditary property.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2011

Modular Orientations of Random and Quasi-Random Regular Graphs.

[BibT_eX]

[DOI]

Pawel Pralat

Comb. Probab. Comput., 2011

Testing perfection is hard

[BibT_eX]

[DOI]

Jacob Fox

CoRR, 2011

Local Correction of Boolean Functions

[BibT_eX]

[DOI]

Amit Weinstein

CoRR, 2011

MIS on the fly

[BibT_eX]

[DOI]

Yehuda Afek

Ziv Bar-Joseph

CoRR, 2011

On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game.

[BibT_eX]

[DOI]

Abbas Mehrabian

Electron. J. Comb., 2011

The Number of f-Matchings in Almost Every Tree is a Zero Residue.

[BibT_eX]

[DOI]

Simi Haber

Electron. J. Comb., 2011

Solving MAX-r-SAT Above a Tight Lower Bound.

[BibT_eX]

[DOI]

Algorithmica, 2011

Beeping a Maximal Independent Set.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Sum of us: strategyproof selection from the selectors.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2011

Economical Graph Discovery.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

List coloring and Euclidean Ramsey Theory.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Typical peak sidelobe level of binary sequences.

[BibT_eX]

[DOI]

Simon Litsyn

Alexander Shpunt

IEEE Trans. Inf. Theory, 2010

Approximate Maximum Parsimony and Ancestral Maximum Likelihood.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2010

The Brunn--Minkowski Inequality and Nontrivial Cycles in the Discrete Torus.

[BibT_eX]

[DOI]

Ohad N. Feldheim

SIAM J. Discret. Math., 2010

The inverse Banzhaf problem.

[BibT_eX]

[DOI]

Paul H. Edelman

Soc. Choice Welf., 2010

Strategyproof Approximation of the Minimax on Networks.

[BibT_eX]

[DOI]

Math. Oper. Res., 2010

A note on regular Ramsey graphs.

[BibT_eX]

[DOI]

Sonny Ben-Shimon

J. Graph Theory, 2010

A note on competitive diffusion through social networks.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Walking in circles.

[BibT_eX]

[DOI]

Discret. Math., 2010

Introduction.

[BibT_eX]

[DOI]

Béla Bollobás

Comb. Probab. Comput., 2010

Practically Stabilizing Atomic Memory

[BibT_eX]

[DOI]

CoRR, 2010

Another Abstraction of the Erdös-Szekeres Happy End Theorem.

[BibT_eX]

[DOI]

Electron. J. Comb., 2010

Brief Announcement: Sharing Memory in a Self-stabilizing Manner.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 24th International Symposium, 2010

Basic network creation games.

[BibT_eX]

[DOI]

Erik D. Demaine

MohammadTaghi Hajiaghayi

Tom Leighton

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.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On Constant Time Approximation of Parameters of Bounded Degree Graphs.

[BibT_eX]

[DOI]

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

Bayesian ignorance.

[BibT_eX]

[DOI]

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

Adversarial Leakage in Games.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

Solving Linear Systems through Nested Dissection.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

A Non-linear Lower Bound for Planar Epsilon-Nets.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Voting Paradoxes.

[BibT_eX]

[DOI]

Proceedings of the COLT 2010, 2010

Testing Boolean Function Isomorphism.

[BibT_eX]

[DOI]

Eric Blais

Proceedings of the Approximation, 2010

2009

Hardness of edge-modification problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Spanning Directed Trees with Many Leaves.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Induced subgraphs with distinct sizes.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2009

Stability-type results for hereditary properties.

[BibT_eX]

[DOI]

J. Graph Theory, 2009

Playing to retain the advantage.

[BibT_eX]

[DOI]

Dan Hefetz

Electron. Notes Discret. Math., 2009

Sizes of Induced Subgraphs of Ramsey Graphs.

[BibT_eX]

[DOI]

József Balogh

Wojciech Samotij

Comb. Probab. Comput., 2009

Economical Elimination of Cycles in the Torus.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2009

Perturbed Identity Matrices Have High Rank: Proof and Applications.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2009

Strategyproof Approximation Mechanisms for Location on Networks

[BibT_eX]

[DOI]

CoRR, 2009

Uniformly cross intersecting families.

[BibT_eX]

[DOI]

Comb., 2009

On the power of two, three and four probes.

[BibT_eX]

[DOI]

Uriel Feige

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

Balanced Hashing, Color Coding and Approximate Counting.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Fast FAST.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Saket Saurabh

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Choice-Memory Tradeoff in Allocations.

[BibT_eX]

[DOI]

Ori Gurel-Gurevich

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Deterministic approximation algorithms for the nearest codeword problem.

[BibT_eX]

[DOI]

Rina Panigrahy

Sergey Yekhanin

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

2008

Color Coding.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Cleaning Regular Graphs with Brushes.

[BibT_eX]

[DOI]

Pawel Pralat

Nicholas C. Wormald

SIAM J. Discret. Math., 2008

Large Nearly Regular Induced Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

What is the furthest graph from a hereditary property?

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2008

The maximum edit distance from hereditary graph properties.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2008

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

An isoperimetric inequality in the universal cover of the punctured plane.

[BibT_eX]

[DOI]

Adi Pinchasi

Rom Pinchasi

Discret. Math., 2008

Breaking the rhythm on graphs.

[BibT_eX]

[DOI]

Jaroslaw Grytczuk

Discret. Math., 2008

Problems and results in extremal combinatorics - II.

[BibT_eX]

[DOI]

Discret. Math., 2008

The Grothendieck constant of random and pseudo-random graphs.

[BibT_eX]

[DOI]

Eli Berger

Discret. Optim., 2008

The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence.

[BibT_eX]

[DOI]

Shmuel Friedland

Electron. J. Comb., 2008

A separation theorem in property testing.

[BibT_eX]

[DOI]

Comb., 2008

Many random walks are faster than one.

[BibT_eX]

[DOI]

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

Weak ε-nets and interval chains.

[BibT_eX]

[DOI]

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

Optimal universal graphs with deterministic embedding.

[BibT_eX]

[DOI]

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

Biomolecular network motif counting and discovery by color coding.

[BibT_eX]

[DOI]

Phuong Dao

Iman Hajirasouliha

Fereydoun Hormozdiari

Süleyman Cenk Sahinalp

Proceedings of the Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), 2008

Optimal Monotone Encodings.

[BibT_eX]

[DOI]

Rani Hod

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

k-Wise Independent Random Graphs.

[BibT_eX]

[DOI]

Asaf Nussboim

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Broadcasting with Side Information.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

The complexity of the outer face in arrangements of random segments.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Polychromatic colorings of plane graphs.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Small Sample Spaces Cannot Fool Low Degree Polynomials.

[BibT_eX]

[DOI]

Ido Ben-Eliezer

Proceedings of the Approximation, 2008

The Probabilistic Method, Third Edition.

[BibT_eX]

Joel H. Spencer

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.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2007

Approximating the maximum clique minor and some subgraph homeomorphism problems.

[BibT_eX]

[DOI]

Andrzej Lingas

Martin Wahlen

Theor. Comput. Sci., 2007

Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2007

Turán's Theorem in the Hypercube.

[BibT_eX]

[DOI]

Anja Krech

Tibor Szabó

SIAM J. Discret. Math., 2007

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.

[BibT_eX]

[DOI]

Ilan Newman

SIAM J. Comput., 2007

On (epsilon, k)-min-wise independent permutations.

[BibT_eX]

[DOI]

Toshiya Itoh

Tatsuya Nagatani

Random Struct. Algorithms, 2007

Sparse universal graphs for bounded-degree graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2007

On graphs with subgraphs having large independence numbers.

[BibT_eX]

[DOI]

J. Graph Theory, 2007

Independent sets in tensor graph powers.

[BibT_eX]

[DOI]

J. Graph Theory, 2007

Maximum directed cuts in acyclic digraphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2007

Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].

[BibT_eX]

[DOI]

Inf. Comput., 2007

Hardness of fully dense problems.

[BibT_eX]

[DOI]

Nir Ailon

Inf. Comput., 2007

Edge Colouring with Delays.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

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

[BibT_eX]

[DOI]

Comb., 2007

Codes And Xor Graph Products.

[BibT_eX]

[DOI]

Comb., 2007

Embedding nearly-spanning bounded degree trees.

[BibT_eX]

[DOI]

Comb., 2007

Testing k-wise and almost k-wise independence.

[BibT_eX]

[DOI]

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

Improved approximation for directed cut problems.

[BibT_eX]

[DOI]

Amit Agarwal

Moses Charikar

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

An elementary construction of constant-degree expanders.

[BibT_eX]

[DOI]

Oded Schwartz

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Balanced Families of Perfect Hash Functions and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Parameterized Algorithms for Directed Maximum Leaf Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Better Algorithms and Bounds for Directed Maximum Leaf Problems.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Finding Disjoint Paths in Expanders Deterministically and Online.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

Can a Graph Have Distinct Regular Partitions?

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2006

Algorithmic construction of sets for k-restrictions.

[BibT_eX]

[DOI]

Dana Moshkovitz

Shmuel Safra

ACM Trans. Algorithms, 2006

Ranking Tournaments.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Regular graphs whose subgraphs tend to be acyclic.

[BibT_eX]

[DOI]

Eitan Bachmat

Random Struct. Algorithms, 2006

A Ramsey-type result for the hypercube.

[BibT_eX]

[DOI]

J. Graph Theory, 2006

Dominating sets in k-majority tournaments.

[BibT_eX]

[DOI]

Graham R. Brightwell

Hal A. Kierstead

Peter Winkler

J. Comb. Theory B, 2006

Multi-Node Graphs: A Framework for Multiplexed Biological Assays.

[BibT_eX]

[DOI]

J. Comput. Biol., 2006

Tracing a single user.

[BibT_eX]

[DOI]

Eur. J. Comb., 2006

Measures of Pseudorandomness for Finite Sequences: Minimal Values.

[BibT_eX]

[DOI]

Carlos Gustavo T. de A. Moreira

Yoshiharu Kohayakawa

Christian Mauduit

Comb. Probab. Comput., 2006

Splitting digraphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

Feasible Schedules for Rotating Transmissions.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

H-Free Graphs of Large Minimum Degree.

[BibT_eX]

[DOI]

Electron. J. Comb., 2006

The Number Of Orientations Having No Fixed Tournament.

[BibT_eX]

[DOI]

Comb., 2006

On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.

[BibT_eX]

[DOI]

Comb., 2006

A combinatorial characterization of the testable graph properties: it's all about regularity.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Tell me who I am: an interactive recommendation system.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Additive Approximation for Edge-Deletion Problems (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Conflict-free colorings of shallow discs.

[BibT_eX]

[DOI]

Shakhar Smorodinsky

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Testing Reed-Muller codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2005

Crossing patterns of semi-algebraic sets.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2005

On a Hypergraph Matching Problem.

[BibT_eX]

[DOI]

Graphs Comb., 2005

Nonrepetitive colorings of graphs.

[BibT_eX]

[DOI]

Jaroslaw Grytczuk

Electron. Notes Discret. Math., 2005

Partitioning multi-dimensional sets in a small number of "uniform" parts

[BibT_eX]

[DOI]

Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2005

Homomorphisms in Graph Property Testing - A Survey

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Tight bounds for shared memory systems accessed by Byzantine processes.

[BibT_eX]

[DOI]

Distributed Comput., 2005

Discrepancy Games.

[BibT_eX]

[DOI]

Electron. J. Comb., 2005

Sharp Bounds For Some Multicolor Ramsey Numbers.

[BibT_eX]

[DOI]

Comb., 2005

Every monotone graph property is testable.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quadratic forms on graphs.

[BibT_eX]

[DOI]

Konstantin Makarychev

Yury Makarychev

Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Admission control to minimize rejections and online set cover with repetitions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

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

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

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

Estimating arbitrary subset sums with few probes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Additive Approximation for Edge-Deletion Problems.

[BibT_eX]

[DOI]

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

A Characterization of the (natural) Graph Properties Testable with One-Sided Error.

[BibT_eX]

[DOI]

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

2004

Dense graphs are antimagic.

[BibT_eX]

[DOI]

J. Graph Theory, 2004

Algorithms with large domination ratio.

[BibT_eX]

[DOI]

Gregory Z. Gutin

J. Algorithms, 2004

New Bounds on Parent-Identifying Codes: The Case of Multiple Parents.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2004

Tight Estimates for Eigenvalues of Regular Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2004

Approximating the cut-norm via Grothendieck's inequality.

[BibT_eX]

[DOI]

Assaf Naor

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

A characterization of easily testable induced subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A general approach to online network optimization problems.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices.

[BibT_eX]

[DOI]

Nathan Srebro

Tommi S. Jaakkola

Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

Learning a Hidden Subgraph.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Edge Coloring with Delays.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2003

Induced subgraphs of prescribed size.

[BibT_eX]

[DOI]

J. Graph Theory, 2003

Partitioning into graphs with only small components.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2003

Generalized hashing and parent-identifying codes.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2003

Maximum cuts and judicious partitions in graphs without short cycles.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2003

Random sampling and approximation of MAX-CSPs.

[BibT_eX]

[DOI]

Wenceslas Fernandez de la Vega

Ravi Kannan

Marek Karpinski

J. Comput. Syst. Sci., 2003

A simple algorithm for edge-coloring bipartite multigraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

A Coding Theory Bound and Zero-Sum Square Matrices.

[BibT_eX]

[DOI]

Simon Litsyn

Graphs Comb., 2003

Factor d-domatic colorings of graphs.

[BibT_eX]

[DOI]

Discret. Math., 2003

Problems and results in extremal combinatorics--I.

[BibT_eX]

[DOI]

Discret. Math., 2003

Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2003

Testing subgraphs in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The online set cover problem.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Smaller explicit superconcentrators.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Testing Low-Degree Polynomials over GF(2(.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2003

2002

Testing k-colorability.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2002

Nonrepetitive colorings of graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2002

On the discrepancy of combinatorial rectangles.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2002

A Ramsey-type problem and the Turán numbers.

[BibT_eX]

[DOI]

J. Graph Theory, 2002

The Moore Bound for Irregular Graphs.

[BibT_eX]

[DOI]

Shlomo Hoory

Nathan Linial

Graphs Comb., 2002

Almost k-wise independence versus k-wise independence.

[BibT_eX]

[DOI]

Oded Goldreich

Yishay Mansour

Electron. Colloquium Comput. Complex., 2002

On partitions of discrete boxes.

[BibT_eX]

[DOI]

Discret. Math., 2002

Game domination number.

[BibT_eX]

[DOI]

Discret. Math., 2002

Covering a hypergraph of subgraphs.

[BibT_eX]

[DOI]

Discret. Math., 2002

The Chromatic Number Of Graph Powers.

[BibT_eX]

[DOI]

Bojan Mohar

Comb. Probab. Comput., 2002

Algorithmic Aspects of Acyclic Edge Colorings.

[BibT_eX]

[DOI]

Algorithmica, 2002

Transversal numbers for hypergraphs arising in geometry.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2002

Voting paradoxes and digraphs realizations.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2002

Random sampling and approximation of MAX-CSP problems.

[BibT_eX]

[DOI]

Wenceslas Fernandez de la Vega

Ravi Kannan

Marek Karpinski

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

Testing satisfiability.

[BibT_eX]

[DOI]

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

Guessing secrets efficiently via list decoding.

[BibT_eX]

[DOI]

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

Explicit Unique-Neighbor Expanders.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Learning a Hidden Matching.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Equireplicate Balanced Binary Codes for Oligo Arrays.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2001

On the maximum number of Hamiltonian paths in tournaments.

[BibT_eX]

[DOI]

Ilan Adler

Sheldon M. Ross

Random Struct. Algorithms, 2001

Acyclic edge colorings of graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2001

Large induced forests in sparse graphs.

[BibT_eX]

[DOI]

Dhruv Mubayi

Robin Thomas

J. Graph Theory, 2001

Unextendible Product Bases.

[BibT_eX]

[DOI]

László Lovász

J. Comb. Theory A, 2001

Parent-Identifying Codes.

[BibT_eX]

[DOI]

Mario Szegedy

J. Comb. Theory A, 2001

Linear Arboricity and Linear k-Arboricity of Regular Graphs.

[BibT_eX]

[DOI]

Vanessa Teague

Nicholas C. Wormald

Graphs Comb., 2001

On the Complexity of Arrangements of Circles in the Plane.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2001

Recursive bounds for perfect hashing.

[BibT_eX]

[DOI]

Emanuela Fachini

Discret. Appl. Math., 2001

Ramsey-type Theorems with Forbidden Subgraphs.

[BibT_eX]

[DOI]

János Pach

József Solymosi

Comb., 2001

Constructing worst case instances for semidefinite programming based approximation algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

An optimal procedure for gap closing in whole genome shotgun sequencing.

[BibT_eX]

[DOI]

Richard Beigel

Simon Kasif

Mehmet Serkan Apaydin

Lance Fortnow

Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Near-optimum Universal Graphs for Graphs with Bounded Degrees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

XML with Data Values: Typechecking Revisited.

[BibT_eX]

[DOI]

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Typechecking XML Views of Relational Databases.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Alexander Lubotzky

Avi Wigderson

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Testing Subgraphs in Large Graphs.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Lower Bounds for Approximations by Low Degree Polynomials Over Zm.

[BibT_eX]

[DOI]

Richard Beigel

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Degrees and choice numbers.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2000

Long cycles in critical graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2000

Decreasing the diameter of bounded degree graphs.

[BibT_eX]

[DOI]

András Gyárfás

Miklós Ruszinkó

J. Graph Theory, 2000

On the Number of Permutations Avoiding a Given Pattern.

[BibT_eX]

[DOI]

Ehud Friedgut

J. Comb. Theory A, 2000

On a Problem in Shuffling.

[BibT_eX]

[DOI]

Kenneth A. Berman

J. Comb. Theory A, 2000

EveryH-decomposition ofKnhas a Nearly Resolvable Alternative.

[BibT_eX]

[DOI]

Eur. J. Comb., 2000

Triangle-free graphs with large chromatic numbers.

[BibT_eX]

[DOI]

Discret. Math., 2000

Bipartite Subgraphs And The Smallest Eigenvalue.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2000

String Quartets In Binary.

[BibT_eX]

[DOI]

János Körner

Angelo Monti

Comb. Probab. Comput., 2000

Locally Thin Set Families.

[BibT_eX]

[DOI]

Emanuela Fachini

János Körner

Comb. Probab. Comput., 2000

Packing Ferrers Shapes.

[BibT_eX]

[DOI]

Miklós Bóna

Joel Spencer

Comb. Probab. Comput., 2000

Scalable Secure Storage when Half the System Is Faulty.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Testing of Clustering.

[BibT_eX]

[DOI]

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

Universality and Tolerance.

[BibT_eX]

[DOI]

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

The Probabilistic Method, Second Edition

[BibT_eX]

[DOI]

Joel H. Spencer

John Wiley, ISBN: 978-0-47172215-1, 2000

1999

Short odd cycles in 4-chromatic graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 1999

Norm-Graphs: Variations and Applications.

[BibT_eX]

[DOI]

Lajos Rónyai

Tibor Szabó

J. Comb. Theory B, 1999

Non-averaging Subsets and Non-vanishing Transversals.

[BibT_eX]

[DOI]

Imre Z. Ruzsa

J. Comb. Theory A, 1999

Coloring Graphs with Sparse Neighborhoods.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1999

On Two Segmentation Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1999

Linear Hash Functions.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Peter Bro Miltersen

Erez Petrank

Gábor Tardos

J. ACM, 1999

Large Sets of Nearly Orthogonal Vectors.

[BibT_eX]

[DOI]

Mario Szegedy

Graphs Comb., 1999

Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.

[BibT_eX]

[DOI]

Peter Hamburger

Eur. J. Comb., 1999

Separable Partitions.

[BibT_eX]

[DOI]

Shmuel Onn

Discret. Appl. Math., 1999

List Coloring of Random and Pseudo-Random Graphs.

[BibT_eX]

[DOI]

Comb., 1999

Refining the Graph Density Condition for the Existence of Almost K-factors.

[BibT_eX]

Ars Comb., 1999

Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths.

[BibT_eX]

[DOI]

Uri Arad

Proceedings of the Randomization, 1999

Tracking Join and Self-Join Sizes in Limited Storage.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Efficient Testing of Large Graphs.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Approximating the independence number via the theta-function.

[BibT_eX]

[DOI]

Nabil Kahalé

Math. Program., 1998

Progressions in Sequences of Nearly Consecutive Integers.

[BibT_eX]

[DOI]

J. Comb. Theory A, 1998

On the Capacity of Digraphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 1998

Bipartite subgraphs of integer weighted graphs.

[BibT_eX]

[DOI]

Eran Halperin

Discret. Math., 1998

Piercing d -Intervals.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1998

T-choosability in Graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

Perfect Matchings in ε-regular Graphs.

[BibT_eX]

[DOI]

Andrzej Rucinski

Electron. J. Comb., 1998

The Shannon Capacity of a Union.

[BibT_eX]

[DOI]

Comb., 1998

On-Line and Off-Line Approximation Algorithms for Vector Covering Problems.

[BibT_eX]

[DOI]

Sergey V. Sevastianov

Arjen P. A. Vestjens

Gerhard J. Woeginger

Algorithmica, 1998

Finding a Large Hidden Clique in a Random Graph.

[BibT_eX]

[DOI]

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

Spectral Techniques in Graph Algorithms.

[BibT_eX]

[DOI]

Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997

A Spectral Technique for Coloring Random 3-Colorable Graphs.

[BibT_eX]

[DOI]

Nabil Kahalé

SIAM J. Comput., 1997

Properly colored Hamilton cycles in edge-colored complete graphs.

[BibT_eX]

[DOI]

Gregory Z. Gutin

Random Struct. Algorithms, 1997

Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs.

[BibT_eX]

[DOI]

Van H. Vu

J. Comb. Theory A, 1997

A Note on Graph Colorings and Graph Polynomials.

[BibT_eX]

[DOI]

Michael Tarsi

J. Comb. Theory B, 1997

On the Degree, Size, and Chromatic Index of a Uniform Hypergraph.

[BibT_eX]

[DOI]

Jeong Han Kim

J. Comb. Theory A, 1997

Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1997

Coins with Arbitrary Weights.

[BibT_eX]

[DOI]

Dmitry N. Kozlov

J. Algorithms, 1997

Constructive Bounds for a Ramsey-Type Problem.

[BibT_eX]

[DOI]

Graphs Comb., 1997

Choosability and fractional chromatic numbers.

[BibT_eX]

[DOI]

Zsolt Tuza

Margit Voigt

Discret. Math., 1997

Packings with large minimum kissing numbers.

[BibT_eX]

[DOI]

Discret. Math., 1997

On the Edge-Expansion of Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1997

Intersecting Systems.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1997

Short Certificates for Tournaments.

[BibT_eX]

[DOI]

Miklós Ruszinkó

Electron. J. Comb., 1997

A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture.

[BibT_eX]

[DOI]

Electron. J. Comb., 1997

The Concentration of the Chromatic Number of Random Graphs.

[BibT_eX]

[DOI]

Comb., 1997

Finding and Counting Given Length Cycles.

[BibT_eX]

[DOI]

Algorithmica, 1997

Improved Parallel Approximation of a Class of Integer Programming Problems.

[BibT_eX]

[DOI]

Aravind Srinivasan

Algorithmica, 1997

Is Linear Hashing Good?

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Peter Bro Miltersen

Erez Petrank

Gábor Tardos

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

Approximation Schemes for Scheduling.

[BibT_eX]

[DOI]

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

1996

Source coding and graph entropies.

[BibT_eX]

[DOI]

Alon Orlitsky

IEEE Trans. Inf. Theory, 1996

A linear time erasure-resilient code with nearly optimal recovery.

[BibT_eX]

[DOI]

Michael Luby

IEEE Trans. Inf. Theory, 1996

Independence numbers of locally sparse graphs and a Ramsey type problem.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1996

Approximate Hypergraph Coloring.

[BibT_eX]

Nord. J. Comput., 1996

Edge-disjoint cycles in regular directed graphs.

[BibT_eX]

[DOI]

Colin McDiarmid

Michael Molloy

J. Graph Theory, 1996

Vertex transversals that dominate.

[BibT_eX]

[DOI]

Michael R. Fellows

Donovan R. Hare

J. Graph Theory, 1996

On k-saturated graphs with restrictions on the degrees.

[BibT_eX]

[DOI]

J. Graph Theory, 1996

H-Factors in Dense Graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1996

Disjoint Directed Cycles.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 1996

Matching Nuts and Bolts Faster.

[BibT_eX]

[DOI]

Phillip G. Bradford

Rudolf Fleischer

Inf. Process. Lett., 1996

2-factors in dense graphs.

[BibT_eX]

[DOI]

Discret. Math., 1996

Bipartite Subgraphs.

[BibT_eX]

[DOI]

Comb., 1996

Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.

[BibT_eX]

[DOI]

Moni Naor

Algorithmica, 1996

Derandomization Via Small Sample Spaces (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1996

The Space Complexity of Approximating the Frequency Moments.

[BibT_eX]

[DOI]

Yossi Matias

Mario Szegedy

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.

[BibT_eX]

[DOI]

Aravind Srinivasan

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

The Geometry of Coin-Weighing Problems.

[BibT_eX]

[DOI]

Dmitry N. Kozlov

Van H. Vu

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

On-line and Off-line Approximation Algorithms for Vector Covering Problems.

[BibT_eX]

[DOI]

János Csirik

Sergey V. Sevastianov

Arjen P. A. Vestjens

Gerhard J. Woeginger

Proceedings of the Algorithms, 1996

1995

Repeated communication and Ramsey graphs.

[BibT_eX]

[DOI]

Alon Orlitsky

IEEE Trans. Inf. Theory, 1995

A Graph-Theoretic Game and Its Application to the k-Server Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

The Acyclic Orientation Game on Random Graphs.

[BibT_eX]

[DOI]

Zsolt Tuza

Random Struct. Algorithms, 1995

Disjoint Systems.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1995

Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.

[BibT_eX]

[DOI]

Alan M. Frieze

Dominic Welsh

Random Struct. Algorithms, 1995

The 123 Theorem and Its Extensions.

[BibT_eX]

J. Comb. Theory A, 1995

epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.

[BibT_eX]

[DOI]

Yishay Mansour

Inf. Process. Lett., 1995

Bounding the Piercing Number.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1995

Covering with Latin Transversals.

[BibT_eX]

[DOI]

Joel Spencer

Prasad Tetali

Discret. Appl. Math., 1995

A Lattice Point Problem and Additive Number Theory.

[BibT_eX]

[DOI]

Moshe Dubiner

Comb., 1995

Derandomized Graph Products.

[BibT_eX]

[DOI]

Comput. Complex., 1995

Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract).

[BibT_eX]

[DOI]

Jeff Edmonds

Michael Luby

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

Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.

[BibT_eX]

[DOI]

Zvi Galil

Moti Yung

Proceedings of the Algorithms, 1995

1994

A lower bound on the expected length of one-to-one codes.

[BibT_eX]

[DOI]

Alon Orlitsky

IEEE Trans. Inf. Theory, 1994

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Planar Separators.

[BibT_eX]

[DOI]

Robin Thomas

SIAM J. Discret. Math., 1994

Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition.

[BibT_eX]

[DOI]

Jehoshua Bruck

SIAM J. Discret. Math., 1994

Random Cayley Graphs and Expanders.

[BibT_eX]

[DOI]

Yuval Roichman

Random Struct. Algorithms, 1994

Subdivided graphs have linear ramsey numbers.

[BibT_eX]

[DOI]

J. Graph Theory, 1994

Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).

[BibT_eX]

[DOI]

Pavel Pudlák

J. Comput. Syst. Sci., 1994

The Algorithmic Aspects of the Regularity Lemma.

[BibT_eX]

[DOI]

J. Algorithms, 1994

Packing of partial designs.

[BibT_eX]

[DOI]

Graphs Comb., 1994

Color-Coding

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case

[BibT_eX]

[DOI]

Alan M. Frieze

Dominic Welsh

Electron. Colloquium Comput. Complex., 1994

Probabilistic methods in coloring and decomposition problems.

[BibT_eX]

[DOI]

Discret. Math., 1994

Perfect Hashing and Probability.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1994

Explicit Ramsey graphs and orthonormal labelings.

[BibT_eX]

[DOI]

Electron. J. Comb., 1994

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A spectral technique for coloring random 3-colorable graphs (preliminary version).

[BibT_eX]

[DOI]

Nabil Kahalé

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Matching Nuts and Bolts.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Alan M. Frieze

Dominic Welsh

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Finding and Counting Given Length Cycles (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1994

1993

Coin-Flipping Games Immune Against Linear-Sized Coalitions.

[BibT_eX]

[DOI]

Moni Naor

SIAM J. Comput., 1993

Addendum to "Simple Construction of Almost k-wise Independent Random Variables".

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1993

On three zero-sum Ramsey-type problems.

[BibT_eX]

[DOI]

J. Graph Theory, 1993

Covering the Cube by Affine Hyperplanes.

[BibT_eX]

[DOI]

Eur. J. Comb., 1993

Bisection of trees and sequences.

[BibT_eX]

[DOI]

Ilia Krasikov

Discret. Math., 1993

On-Line Steine Trees in the Euclidean Plane.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1993

Threshold Functions for H-factors.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1993

Routing permutations on graphs via matchings.

[BibT_eX]

[DOI]

Fan R. K. Chung

Ronald L. Graham

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

Scale-sensitive Dimensions, Uniform Convergence, and Learnability

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Disjoint Systems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algebraic Coding, 1993

Long Non-Crossing Configurations in the Plane.

[BibT_eX]

[DOI]

Sridhar Rajagopalan

Subhash Suri

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Can Visibility Graphs be Represented Compactly?

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1992

Simple Construction of Almost k-wise Independent Random Variables.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

The String Chromatic Number of a Graph.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

Single Round Simulation on Radio Networks.

[BibT_eX]

[DOI]

J. Algorithms, 1992

AlmostH-factors in dense graphs.

[BibT_eX]

[DOI]

Graphs Comb., 1992

Generalized sum graphs.

[BibT_eX]

[DOI]

Edward R. Scheinerman

Graphs Comb., 1992

Spanning subgraphs of random graphs.

[BibT_eX]

[DOI]

Graphs Comb., 1992

Partitioning a rectangle into small perimeter rectangles.

[BibT_eX]

[DOI]

Discret. Math., 1992

Transmitting in the n-Dimensional Cube.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1992

Point Selections and Weak e-Nets for Convex Hulls.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1992

Choice Numbers of Graphs: a Probabilistic Approach.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 1992

Colorings and orientations of graphs.

[BibT_eX]

[DOI]

Michael Tarsi

Comb., 1992

Star arboricity.

[BibT_eX]

[DOI]

Colin McDiarmid

Bruce A. Reed

Comb., 1992

Comparison-Sorting and Selecting in Totally Monotone Matrices.

[BibT_eX]

[DOI]

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)

[BibT_eX]

[DOI]

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

Witnesses for Boolean Matrix Multiplication and for Shortest Paths

[BibT_eX]

[DOI]

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

The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)

[BibT_eX]

[DOI]

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

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths

[BibT_eX]

[DOI]

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

Random Cayley Graphs and Expanders (Abstract).

[BibT_eX]

[DOI]

Yuval Roichman

Proceedings of the Expanding Graphs, 1992

Piercing Convex Sets.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

On-Line Steiner Trees in the Euclidean Plane.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

The Probabilistic Method

[BibT_eX]

[DOI]

Joel Spencer

John Wiley, ISBN: 0-471-53588-5, 1992

1991

Acyclic Coloring of Graphs.

[BibT_eX]

[DOI]

Colin McDiarmid

Bruce A. Reed

Random Struct. Algorithms, 1991

Additive bases of vector spaces over prime fields.

[BibT_eX]

[DOI]

Nathan Linial

Roy Meshulam

J. Comb. Theory A, 1991

Multicolored forests in bipartite decompositions of graphs.

[BibT_eX]

[DOI]

Richard A. Brualdi

Bryan L. Shader

J. Comb. Theory B, 1991

Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.

[BibT_eX]

[DOI]

László Babai

Hiroshi Suzuki

J. Comb. Theory A, 1991

A Lower Bound for Radio Broadcast.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

Efficient Simulation of Finite Automata by Neural Nets.

[BibT_eX]

[DOI]

A. K. Dewdney

Teunis J. Ott

J. ACM, 1991

Set systems with no union of cardinality 0 modulom.

[BibT_eX]

[DOI]

Graphs Comb., 1991

Ramsey graphs contain many distinct induced subgraphs.

[BibT_eX]

[DOI]

András Hajnal

Graphs Comb., 1991

On the second eigenvalue of a graph.

[BibT_eX]

[DOI]

Discret. Math., 1991

On the Exponent of the All Pairs Shortest Path Problem

[BibT_eX]

Zvi Galil

Oded Margalit

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

A parallel algorithmic version of the Local Lemma

[BibT_eX]

[DOI]

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).

[BibT_eX]

[DOI]

Proceedings of the On-Line Algorithms, 1991

1990

Linear Circuits over GF(2).

[BibT_eX]

[DOI]

Mauricio Karchmer

Avi Wigderson

SIAM J. Comput., 1990

The Number of Spanning Trees in Regular Graphs.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1990

Ramsey graphs cannot be defined by real polynomials.

[BibT_eX]

[DOI]

J. Graph Theory, 1990

Generating Pseudo-Random Permutations and Maximum Flow Algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

Transversal numbers of uniform hypergraphs.

[BibT_eX]

[DOI]

Graphs Comb., 1990

Not All Graphs are Segment T-graphs.

[BibT_eX]

[DOI]

Edward R. Scheinerman

Eur. J. Comb., 1990

The CW-Inequalities for Vectors in l1.

[BibT_eX]

[DOI]

Eur. J. Comb., 1990

Universal sequences for complete graphs.

[BibT_eX]

[DOI]

Yiftach Ravid

Discret. Appl. Math., 1990

The maximum number of Hamiltonian paths in tournaments.

[BibT_eX]

[DOI]

Comb., 1990

A Separator Theorem for Graphs with an Excluded Minor and its Applications

[BibT_eX]

[DOI]

Robin Thomas

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)

[BibT_eX]

[DOI]

Moni Naor

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

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

[BibT_eX]

[DOI]

Nimrod Megiddo

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

Simple Constructions of Almost k-Wise Independent Random Variables

[BibT_eX]

[DOI]

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

1989

On Neciporuk's Theorem for Branching Programs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Finding an Approximate Maximum.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

A counterexample to the rank-coloring conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 1989

Ascending waves.

[BibT_eX]

[DOI]

Joel H. Spencer

J. Comb. Theory A, 1989

Cycles of length 0 modulo k in directed graphs.

[BibT_eX]

[DOI]

Nathan Linial

J. Comb. Theory B, 1989

Combinatorial reconstruction problems.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1989

Legitimate colorings of projective planes.

[BibT_eX]

[DOI]

Graphs Comb., 1989

Sub-Ramsey numbers for arithmetic progressions.

[BibT_eX]

[DOI]

Zsolt Tuza

Graphs Comb., 1989

Graphs with a small number of distinct induced subgraphs.

[BibT_eX]

[DOI]

Béla Bollobás

Discret. Math., 1989

The star arboricity of graphs.

[BibT_eX]

[DOI]

I. Algor

Discret. Math., 1989

The Maximum Size of a Convex Polygon in a Restricted Set in the Plane.

[BibT_eX]

[DOI]

William R. Pulleyblank

Discret. Comput. Geom., 1989

Cutting Disjoint Disks by Straight Lines.

[BibT_eX]

[DOI]

William R. Pulleyblank

Discret. Comput. Geom., 1989

Disjoint Edges in Geometric Graphs.

[BibT_eX]

[DOI]

Paul Erdös

Discret. Comput. Geom., 1989

A nowhere-zero point in liner mappings.

[BibT_eX]

[DOI]

Michael Tarsi

Comb., 1989

Biased Coins and Randomized Algorithms.

[BibT_eX]

Michael O. Rabin

Adv. Comput. Res., 1989

On the Complexity of Radio Communication (Extended Abstract)

[BibT_eX]

[DOI]

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

1988

Balancing sets of vectors.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1988

Sorting, Approximate Sorting, and Searching in Rounds.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1988

The average size of an independent set in graphs with a given chromatic number.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1988

Meanders and Their Applications in Lower Bounds Arguments.

[BibT_eX]

[DOI]

Wolfgang Maass

J. Comput. Syst. Sci., 1988

Every 8-uniform 8-regular hypergraph is 2-colorable.

[BibT_eX]

[DOI]

Z. Bregman

Graphs Comb., 1988

Explicit construction of linear sized tolerant networks.

[BibT_eX]

[DOI]

Fan R. K. Chung

Discret. Math., 1988

Sums of subsequences modulo prime powers.

[BibT_eX]

[DOI]

Discret. Math., 1988

On sums of subsets of a set of integers.

[BibT_eX]

[DOI]

Gregory Freiman

Comb., 1988

Parallel Comparison Algorithms for Approximation Problems

[BibT_eX]

[DOI]

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

1987

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

[BibT_eX]

[DOI]

J. Graph Theory, 1987

Better Expanders and Superconcentrators.

[BibT_eX]

[DOI]

Zvi Galil

V. D. Milman

J. Algorithms, 1987

Large induced degenerate subgraphs.

[BibT_eX]

[DOI]

Jeff Kahn

Graphs Comb., 1987

On the kernel of intersecting families.

[BibT_eX]

[DOI]

Graphs Comb., 1987

The smallets n-uniform hypergraph with positive discrepancy.

[BibT_eX]

[DOI]

Comb., 1987

The monotone circuit complexity of Boolean functions.

[BibT_eX]

[DOI]

Ravi B. Boppana

Comb., 1987

On Disseminating Information Reliably without Broadcasting.

[BibT_eX]

Amnon Barak

Udi Manber

Proceedings of the 7th International Conference on Distributed Computing Systems, 1987

The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension.

[BibT_eX]

[DOI]

David Haussler

Emo Welzl

Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986

The longest cycle of a graph with a large minimal degree.

[BibT_eX]

[DOI]

J. Graph Theory, 1986

The number of small semispaces of a finite set of points in the plane.

[BibT_eX]

[DOI]

Ervin Györi

J. Comb. Theory A, 1986

Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory.

[BibT_eX]

[DOI]

Kenneth A. Berman

J. Comb. Theory A, 1986

A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.

[BibT_eX]

[DOI]

László Babai

Alon Itai

J. Algorithms, 1986

Decomposition of the completer-graph into completer-partiter-graphs.

[BibT_eX]

[DOI]

Graphs Comb., 1986

Extremal Problems Concerning Transformations of the Set of Edges of the Complete Graph.

[BibT_eX]

[DOI]

Eur. J. Comb., 1986

On the intersection of edges of a geometric graph by straight lines.

[BibT_eX]

[DOI]

Micha A. Perles

Discret. Math., 1986

Explicit construction of exponential sized families of k-independent sets.

[BibT_eX]

[DOI]

Discret. Math., 1986

Covering a Square by Small Perimeter Rectangles.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1986

Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory.

[BibT_eX]

[DOI]

Comb., 1986

Covering graphs by the minimum number of equivalence relations.

[BibT_eX]

[DOI]

Comb., 1986

Eigenvalues and expanders.

[BibT_eX]

[DOI]

Comb., 1986

Meanders, Ramsey Theory and Lower Bounds for Branching Programs

[BibT_eX]

[DOI]

Wolfgang Maass

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

Tight Complexity Bounds for Parallel Comparison Sorting

[BibT_eX]

[DOI]

Uzi Vishkin

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

1985

lambda1, Isoperimetric inequalities for graphs, and superconcentrators.

[BibT_eX]

[DOI]

V. D. Milman

J. Comb. Theory B, 1985

Even edge colorings of a graph.

[BibT_eX]

[DOI]

Yoshimi Egawa

J. Comb. Theory B, 1985

An Extremal Problem for Sets with Applications to Graph Theory.

[BibT_eX]

[DOI]

J. Comb. Theory A, 1985

The maximum number of disjoint pairs in a family of subsets.

[BibT_eX]

[DOI]

Peter Frankl

Graphs Comb., 1985

Hypergraphs with high chromatic number.

[BibT_eX]

[DOI]

Graphs Comb., 1985

Asynchronous threshold networks.

[BibT_eX]

[DOI]

Graphs Comb., 1985

A Simple Proof of the Upper Bound Theorem.

[BibT_eX]

[DOI]

Eur. J. Comb., 1985

Separating Pairs of Points by Standard Boxes.

[BibT_eX]

[DOI]

Eur. J. Comb., 1985

An Application of Graph Theory to Additive Number Theory.

[BibT_eX]

[DOI]

Paul Erdös

Eur. J. Comb., 1985

Expanders, Sorting in Rounds and Superconcentrators of Limited Depth

[BibT_eX]

[DOI]

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Geometrical Realization of Set Systems and Probabilistic Communication Complexity

[BibT_eX]

[DOI]

Peter Frankl

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.

[BibT_eX]

[DOI]

Shmuel Friedland

J. Comb. Theory B, 1984

Regular subgraphs of almost regular graphs.

[BibT_eX]

[DOI]

Shmuel Friedland

J. Comb. Theory B, 1984

A note on subdigraphs of digraphs with large outdegrees.

[BibT_eX]

[DOI]

Discret. Math., 1984

Eigenvalues, Expanders and Superconcentrators (Extended Abstract)

[BibT_eX]

[DOI]

V. D. Milman

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.

[BibT_eX]

[DOI]

J. Graph Theory, 1983

On the density of sets of vectors.

[BibT_eX]

[DOI]