2024
On the connectivity and diameter of geodetic graphs.
Eur. J. Comb., February, 2024
The Rank-Ramsey Problem and the Log-Rank Conjecture.
CoRR, 2024
2023
New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes.
IEEE Trans. Inf. Theory, May, 2023
Discret. Comput. Geom., March, 2023
Irreducible nonmetrizable path systems in graphs.
J. Graph Theory, 2023
An Elementary Proof of the First LP Bound on the Rate of Binary Codes.
CoRR, 2023
2022
Geodesic Geometry on Graphs.
Discret. Comput. Geom., 2022
Linear Programming Hierarchies in Coding Theory: Dual Solutions.
CoRR, 2022
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes.
CoRR, 2022
Bounds on Unique-Neighbor Codes.
CoRR, 2022
On the Local Structure of Oriented Graphs - a Case Study in Flag Algebras.
Electron. J. Comb., 2022
2021
A randomized construction of high girth regular graphs.
Random Struct. Algorithms, 2021
An Improved Protocol for the Exactly-N Problem.
Proceedings of the 36th Computational Complexity Conference, 2021
2020
On the weight distribution of random binary linear codes.
Random Struct. Algorithms, 2020
Asymptotically Almost Every 2r-Regular Graph Has an Internal Partition.
Graphs Comb., 2020
Expander Graphs - Both Local and Global.
Comb., 2020
PWAS: Proteome-Wide Association Study.
Proceedings of the Research in Computational Molecular Biology, 2020
Functional Evolutionary Modeling Exposes Overlooked Protein-Coding Genes Involved in Cancer.
Proceedings of the Bioinformatics Research and Applications - 16th International Symposium, 2020
2019
Enumeration and randomized constructions of hypertrees.
Random Struct. Algorithms, 2019
A cell-based probabilistic approach unveils the concerted action of miRNAs.
PLoS Comput. Biol., 2019
A King in every two consecutive tournaments.
CoRR, 2019
On the Communication Complexity of High-Dimensional Permutations.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
2018
Monotone Subsequences in High-Dimensional Permutations.
Comb. Probab. Comput., 2018
2017
On the Rigidity of Sparse Random Graphs.
J. Graph Theory, 2017
On The Communication Complexity of High-Dimensional Permutations.
CoRR, 2017
2016
The threshold for d-collapsibility in random complexes.
Random Struct. Algorithms, 2016
On the Number of 4-Cycles in a Tournament.
J. Graph Theory, 2016
On the Local Profiles of Trees.
J. Graph Theory, 2016
Internal Partitions of Regular Graphs.
J. Graph Theory, 2016
Invariants of Random Knots and Links.
Discret. Comput. Geom., 2016
On the densities of cliques and independent sets in graphs.
Comb., 2016
2015
When does the top homology of a random simplicial complex vanish?
Random Struct. Algorithms, 2015
Graphs with Few 3-Cliques and 3-Anticliques are 3-Universal.
J. Graph Theory, 2015
Triply Existentially Complete Triangle-Free Graphs.
J. Graph Theory, 2015
A Note on the Inducibility of 4-Vertex Graphs.
Graphs Comb., 2015
2014
SIAM J. Discret. Math., 2014
On the 3-Local Profiles of Graphs.
J. Graph Theory, 2014
On the Vertices of the d-Dimensional Birkhoff Polytope.
Discret. Comput. Geom., 2014
Market Share Indicates Quality.
CoRR, 2014
On Regular Hypergraphs of High Girth.
Electron. J. Comb., 2014
An upper bound on the number of high-dimensional permutations.
Comb., 2014
Entropy-driven partitioning of the hierarchical protein space.
Bioinform., 2014
From average case complexity to improper learning complexity.
Proceedings of the Symposium on Theory of Computing, 2014
The Complexity of Learning Halfspaces using Generalized Linear Methods.
Proceedings of The 27th Conference on Learning Theory, 2014
2013
An upper bound on the number of Steiner triple systems.
Random Struct. Algorithms, 2013
On High-Dimensional Acyclic Tournaments.
Discret. Comput. Geom., 2013
Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes.
Discret. Comput. Geom., 2013
On the practically interesting instances of MAXCUT.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013
More data speeds up training time in learning halfspaces over sparse vectors.
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
2012
ProtoNet 6.0: organizing 10 million protein sequences in a compact hierarchical family tree.
Nucleic Acids Res., 2012
Tight products and graph expansion.
J. Graph Theory, 2012
On the Lipschitz constant of the RSK correspondence.
J. Comb. Theory A, 2012
Strong convergence in posets.
J. Comb. Theory A, 2012
The error rate of learning halfspaces using Kernel-SVMs
CoRR, 2012
Clustering is difficult only when it does not matter
CoRR, 2012
No justified complaints: on fair sharing of multiple resources.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012
2011
Eigenvectors of random graphs: Nodal Domains.
Random Struct. Algorithms, 2011
The Expected Genus of a Random Chord Diagram.
Discret. Comput. Geom., 2011
Generative probabilistic models for protein-protein interaction networks - the biclique perspective.
Bioinform., 2011
Recovering key biological constituents through sparse representation of gene expression.
Bioinform., 2011
Proceedings of the Distributed Computing - 25th International Symposium, 2011
The dynamics of reputation systems.
Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), 2011
Geometric Interpretation of Gene Expression by Sparse Reconstruction of Transcript Profiles.
Proceedings of the Research in Computational Molecular Biology, 2011
2010
Word maps and spectra of random graph lifts.
Random Struct. Algorithms, 2010
Sum Complexes - a New Family of Hypertrees.
Discret. Comput. Geom., 2010
Tight products and Expansion
CoRR, 2010
2009
Lower bounds in communication complexity based on factorization norms.
Random Struct. Algorithms, 2009
Are stable instances easy?
Electron. Colloquium Comput. Complex., 2009
Learning Complexity vs Communication Complexity.
Comb. Probab. Comput., 2009
2008
Graph Colouring with No Large Monochromatic Components.
Comb. Probab. Comput., 2008
2007
EVEREST: a collection of evolutionary conserved protein domains.
Nucleic Acids Res., 2007
Graph coloring with no large monochromatic components.
Electron. Notes Discret. Math., 2007
Complexity measures of sign matrices.
Comb., 2007
2006
Minors in lifts of graphs.
Random Struct. Algorithms, 2006
On the expansion rate of Margulis expanders.
J. Comb. Theory B, 2006
Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis.
J. Comput. Biol., 2006
How Neighborly Can a Centrally Symmetric Polytope Be?
Discret. Comput. Geom., 2006
Random Lifts of Graphs: Edge Expansion.
Comb. Probab. Comput., 2006
Homological Connectivity Of Random 2-Complexes.
Comb., 2006
Lifts, Discrepancy and Nearly Optimal Spectral Gap*.
Comb., 2006
EVEREST: automatic identification and classification of protein domains in all protein sequences.
BMC Bioinform., 2006
2005
ProtoNet 4.0: A hierarchical classification of one million protein sequences.
Nucleic Acids Res., 2005
Essential covers of the cube by hyperplanes.
J. Comb. Theory A, 2005
A counterexample to a conjecture of Björner and Lovász on the <i>chi</i>-coloring complex.
J. Comb. Theory B, 2005
Monotone maps, sphericity and bounded second eigenvalue.
J. Comb. Theory B, 2005
Some Low Distortion Metric Ramsey Problems.
Discret. Comput. Geom., 2005
Random Lifts Of Graphs: Perfekt Matchings.
Comb., 2005
2004
Colorings of the d-regular infinite tree.
J. Comb. Theory B, 2004
Low dimensional embeddings of ultrametrics.
Eur. J. Comb., 2004
Metric Embeddings--Beyond One-Dimensional Distortion.
Discret. Comput. Geom., 2004
The One-Round Voronoi Game.
Discret. Comput. Geom., 2004
Ramanujan Signing of Regular Graphs.
Comb. Probab. Comput., 2004
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
ProtoNet: hierarchical classification of the protein space.
Nucleic Acids Res., 2003
The Euclidean Distortion of Complete Binary Trees.
Discret. Comput. Geom., 2003
On metric ramsey-type phenomena.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
2002
Random lifts of graphs: Independence and chromatic number.
Random Struct. Algorithms, 2002
A Continuous Analogue of the Girth Problem.
J. Comb. Theory B, 2002
An Extremal Problem on Degree Sequences of Graphs.
Graphs Comb., 2002
The Moore Bound for Irregular Graphs.
Graphs Comb., 2002
Linear Codes and Character Sums.
Comb., 2002
Random Graph Coverings I: General Theory and Graph Connectivity.
Comb., 2002
Girth and euclidean distortion.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
The metric space of proteins-comparative study of clustering algorithms.
Proceedings of the Tenth International Conference on Intelligent Systems for Molecular Biology, 2002
Finite metric spaces: combinatorics, geometry and algorithms.
Proceedings of the 18th Annual Symposium on Computational Geometry, 2002
2001
Neighborhood Preserving Hashing and Approximate Queries.
SIAM J. Discret. Math., 2001
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
2000
ProtoMap: automatic classification of protein sequences and hierarchy of protein families.
Nucleic Acids Res., 2000
Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders.
J. Comb. Theory B, 2000
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Comb., 2000
On the Hardness of Approximating the Chromatic Number.
Comb., 2000
1999
A Note on the Influence of an epsilon-Biased Random Source.
J. Comput. Syst. Sci., 1999
The Linear-Array Conjecture in Communication Complexity Is False.
Comb., 1999
Competitive Optimal On-Line Leasing.
Algorithmica, 1999
1998
Fault-Tolerant Computation in the Full Information Model.
SIAM J. Comput., 1998
Trees and Euclidean Metrics.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
A Map of the Protein Space: An Automatic Hierarchical Classification of all Protein Sequences.
Proceedings of the 6th International Conference on Intelligent Systems for Molecular Biology (ISMB-98), Montréal, Québec, Canada, June 28, 1998
1997
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.
Comb., 1997
1996
Witness Sets for Families of Binary Vectors.
J. Comb. Theory A, 1996
Central Points for Sets in Rn (or: the Chocolate Ice-Cream Problem).
Discret. Comput. Geom., 1996
Inclusion-Exclusion: Exact and Approximate.
Comb., 1996
1995
On the distance distribution of codes.
IEEE Trans. Inf. Theory, 1995
The Geometry of Graphs and Some of its Algorithmic Applications.
Comb., 1995
Fast Perfect-Information Leader-Election Protocols with Linear Immunity.
Comb., 1995
1994
Local and Global Clique Numbers.
J. Comb. Theory B, 1994
Spectral Properties of Threshold Functions.
Comb., 1994
1993
On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels.
IEEE Trans. Inf. Theory, 1993
Constant Depth Circuits, Fourier Transform, and Learnability.
J. ACM, 1993
Combinatorial characterization of read-once formulae.
Discret. Math., 1993
Discret. Comput. Geom., 1993
Local-Global Phenomena in Graphs.
Comb. Probab. Comput., 1993
Low diameter graph decompositions.
Comb., 1993
The influence of large coalitions.
Comb., 1993
Fast perfection-information leader-election protocol with linear immunity.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993
Sphere Packing and Local Majorities in Graphs.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993
1992
Locality in Distributed Graph Algorithms.
SIAM J. Comput., 1992
Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties.
J. Comb. Theory B, 1992
The Equivalence of Two Problems on the Cube.
J. Comb. Theory A, 1992
Single Round Simulation on Radio Networks.
J. Algorithms, 1992
An Optimal On-Line Algorithm for Metrical Task System.
J. ACM, 1992
1991
Results on Learnability and the Vapnik-Chervonenkis Dimension
Inf. Comput., January, 1991
Additive bases of vector spaces over prime fields.
J. Comb. Theory A, 1991
A Lower Bound for Radio Broadcast.
J. Comput. Syst. Sci., 1991
Balancing extensions via Brunn-Minkowski.
Comb., 1991
A Lower Bound on the Area of Permutation Layouts.
Algorithmica, 1991
Decomposing Graphs into Regions of Small Diameter.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991
Fault-tolerant Computation in the Full Information Model (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
Improved Routing Strategies with Succinct Tables.
J. Algorithms, 1990
Approximate inclusion-exclusion.
Comb., 1990
1989
Bounds on Universal Sequences.
SIAM J. Comput., 1989
Cycles of length 0 modulo <i>k</i> in directed graphs.
J. Comb. Theory B, 1989
Interpolation Between Bases and the Shuffle Exchange Network.
Eur. J. Comb., 1989
Some extremal problems arising form discrete control processes.
Comb., 1989
Collective Coin Flipping.
Adv. Comput. Res., 1989
Compact Distributed Data Structures for Adaptive Routing (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
On the Complexity of Radio Communication (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Graph Products and Chromatic Numbers
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
Some Bounds for the Banzhaf Index and Other Semivalues.
Math. Oper. Res., 1988
Matroidal bijections between graphs.
J. Comb. Theory B, 1988
Rubber bands, convex embeddings and graph connectivity.
Comb., 1988
Optima of dual integer linear programs.
Comb., 1988
Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
The Influence of Variables on Boolean Functions (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
Results on Learnability and the Vapnick-Chervonenkis Dimension.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988
1987
Extremal problems on permutations under cyclic equivalence.
Discret. Math., 1987
Imperfect Random Sources and Discrete Controlled Processes
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987
An Optimal Online Algorithm for Metrical Task Systems
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987
Distributive Graph Algorithms-Global Solutions from Local Data
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987
1986
Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas.
J. Comb. Theory A, 1986
Graph coloring and monotone functions on posets.
Discret. Math., 1986
Legal coloring of graphs.
Comb., 1986
A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
1985
Deciding Hypergraph 2-Colourability by H-Resolution.
Theor. Comput. Sci., 1985
Every Poset Has a Central Element.
J. Comb. Theory A, 1985
Searching Ordered Structures.
J. Algorithms, 1985
Dual Integer Linear Programs and the Relationship between their Optima
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
Multi-Layer Grid Embeddings
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
The Information-Theoretic Bound is Good for Merging.
SIAM J. Comput., 1984
Graph decompositions without isolates.
J. Comb. Theory B, 1984
1983
Largest digraphs contained in all n-tournaments.
Comb., 1983
Information Bounds Are Good for Search Problems on Ordered Data Structures
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
1982
The Counterfeit Coin Problem Revisited.
SIAM J. Comput., 1982
A New Derivation of the Counting Formula for Young Tableaux.
J. Comb. Theory A, 1982
1981
Extending the Greene-Kleitman Theorem to Directed Graphs.
J. Comb. Theory A, 1981
On Petersen's graph theorem.
Discret. Math., 1981
1978
בעיות פירוק וכיסוי בתורת הגרפים (Decomposition and covering problems in graph theory.).
PhD thesis, 1978
Covering digraphs by paths.
Discret. Math., 1978
1976
A lower bound for the circumference of a graph.
Discret. Math., 1976
