Piotr Berman

According to our database1, Piotr Berman authored at least 174 papers between 1978 and 2016.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2016
Tolerant Testers of Image Properties.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

The Power and Limitations of Uniform Samples in Testing Properties of Figures.
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Testing Convexity of Figures Under the Uniform Distribution.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Constant-Time Testing and Learning of Image Properties.
CoRR, 2015

The Distributed Selection Problem and the AKS Sorting Network.
CoRR, 2015

2014
HybridPlan: a capacity planning technique for projecting storage requirements in hybrid storage systems.
The Journal of Supercomputing, 2014

Approximation Algorithms for Min-Max Generalization Problems.
ACM Trans. Algorithms, 2014

Steiner transitive-closure spanners of low-dimensional posets.
Combinatorica, 2014

On the Computational Complexity of Measuring Global Stability of Banking Networks.
Algorithmica, 2014

Lp-testing.
Proceedings of the Symposium on Theory of Computing, 2014

2013
Approximation algorithms for spanner problems and Directed Steiner Forest.
Inf. Comput., 2013

2012
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.
Algorithmica, 2012

Improving the performance of k-means clustering through computation skipping and data locality optimizations.
Proceedings of the Computing Frontiers Conference, CF'12, 2012

Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Optimizing sensor movement planning for energy efficiency.
TOSN, 2011

On Systemic Stability of Banking Networks
CoRR, 2011

Approximating the Online Set Multicover Problems Via Randomized Winnowing
CoRR, 2011

On Approximating Four Covering and Packing Problems
CoRR, 2011

HybridStore: A Cost-Efficient, High-Performance Storage System Combining SSDs and HDDs.
Proceedings of the MASCOTS 2011, 2011

Improved Approximation for the Directed Spanner Problem.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Steiner Transitive-Closure Spanners of Low-Dimensional Posets.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

O(1)-Approximations for Maximum Movement Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Steiner Transitive-Closure Spanners of d-Dimensional Posets
CoRR, 2010

Successes and Failures of Elegant Algorithms in Computational Biology.
Proceedings of the Bioinformatics Research and Applications, 6th International Symposium, 2010

A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Efficient Alignments of Metabolic Networks with Bounded Treewidth.
Proceedings of the ICDMW 2010, 2010

Finding Sparser Directed Spanners.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.
Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

Approximation Algorithms for Min-Max Generalization Problems.
Proceedings of the Approximation, 2010

2009
On approximating four covering and packing problems.
J. Comput. Syst. Sci., 2009

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications
CoRR, 2009

Consistent Sets of Secondary Structures in Proteins.
Algorithmica, 2009

1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Approximating Transitive Reductions for Directed Networks.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Aligning Two Genomic Sequences That Contain Duplications.
Proceedings of the Comparative Genomics, International Workshop, 2009

2008
Approximating the online set multicover problems via randomized winnowing.
Theor. Comput. Sci., 2008

Improving Strand Pairing Prediction through Exploring Folding Cooperativity.
IEEE/ACM Trans. Comput. Biology Bioinform., 2008

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two.
Electronic Colloquium on Computational Complexity (ECCC), 2008

A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two
CoRR, 2008

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
CoRR, 2008

Approximating Transitivity in Directed Networks
CoRR, 2008

On cycles in the transcription network of Saccharomyces cerevisiae.
BMC Systems Biology, 2008

HCV Quasispecies Assembly Using Network Flows.
Proceedings of the Bioinformatics Research and Applications, 2008

Fast Alignments of Metabolic Networks.
Proceedings of the 2008 IEEE International Conference on Bioinformatics and Biomedicine, 2008

2007
Bidding Protocols for Deploying Mobile Sensors.
IEEE Trans. Mob. Comput., 2007

Optimal trade-off for Merkle tree traversal.
Theor. Comput. Sci., 2007

Approximating Huffman codes in parallel.
J. Discrete Algorithms, 2007

On constructing an optimal consensus clustering from multiple clusterings.
Inf. Process. Lett., 2007

Approximating Transitive Reductions for Directed Networks.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Approximating the Online Set Multicover Problems Via Randomized Winnowing.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Computational complexity of some restricted instances of 3-SAT.
Discrete Applied Mathematics, 2007

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks.
Discrete Applied Mathematics, 2007

The inverse protein folding problem on 2D and 3D lattices.
Discrete Applied Mathematics, 2007

HomologMiner: looking for homologous genomic groups in whole genomes.
Bioinformatics, 2007

Foreword.
Algorithmica, 2007

Faster Approximation of Distances in Graphs.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Bringing Folding Pathways into Strand Pairing Prediction.
Proceedings of the Algorithms in Bioinformatics, 7th International Workshop, 2007

Packing to angles and sectors.
Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

2006
Packing to angles and sectors.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Linear-Time Algorithm for Studying Genetic Variation.
Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

Controlling Size When Aligning Multiple Genomic Sequences with Duplications.
Proceedings of the Algorithms in Bioinformatics, 6th International Workshop, 2006

8/7-approximation algorithm for (1, 2)-TSP.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees.
Proceedings of the Computer Science, 2006

2005
Tight approximability results for test set problems in bioinformatics.
J. Comput. Syst. Sci., 2005

8/7-Approximation Algorithm for (1,2)-TSP
Electronic Colloquium on Computational Complexity (ECCC), 2005

On the Vehicle Routing Problem.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Approximating the Online Set Multicover Problems via Randomized Winnowing.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Optimizing sensor movement planning for energy efficiency.
Proceedings of the 2005 International Symposium on Low Power Electronics and Design, 2005

Optimal Trade-Off for Merkle Tree Traversal.
Proceedings of the E-business and Telecommunication Networks, 2005

2004
Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search.
Journal of Computational Biology, 2004

Computational Complexity of Some Restricted Instances of 3SAT
Electronic Colloquium on Computational Complexity (ECCC), 2004

Optimal Trade-Off for Merkle Tree Traversal
Electronic Colloquium on Computational Complexity (ECCC), 2004

Power efficient monitoring management in sensor networks.
Proceedings of the 2004 IEEE Wireless Communications and Networking Conference , 2004

Tight Approximability Results for Test Set Problems in Bioinformatics.
Proceedings of the Algorithm Theory, 2004

The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices.
Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks.
Proceedings of the Approximation, 2004

2003
Approximation algorithms for MAX-MIN tiling.
J. Algorithms, 2003

Approximability of Hypergraph Minimum Bisection.
Electronic Colloquium on Computational Complexity (ECCC), 2003

Approximation Hardness of Short Symmetric Instances of MAX-3SAT.
Electronic Colloquium on Computational Complexity (ECCC), 2003

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Electronic Colloquium on Computational Complexity (ECCC), 2003

Improved Approximation Lower Bounds on Small Occurrence Optimization
Electronic Colloquium on Computational Complexity (ECCC), 2003

Aligning two fragmented sequences.
Discrete Applied Mathematics, 2003

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

2002
Exact Size of Binary Space Partitionings and Improved Rectangle Tiling Algorithms.
SIAM J. Discrete Math., 2002

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
J. Comput. Syst. Sci., 2002

Approximating Huffman Codes in Parallel
Electronic Colloquium on Computational Complexity (ECCC), 2002

Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search.
Proceedings of the Algorithms in Bioinformatics, Second International Workshop, 2002

Approximating minimum unsatisfiability of linear equations.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Simple approximation algorithm for nonoverlapping local alignments.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Slice and dice: a simple, improved approximate tiling recipe.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Aligning Two Fragmented Sequences.
Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002

Approximating Huffman Codes in Parallel.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

1.375-Approximation Algorithm for Sorting by Reversals.
Proceedings of the Algorithms, 2002

2001
Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles.
J. Algorithms, 2001

Improved Approximations for General Minimum Cost Scheduling
Electronic Colloquium on Computational Complexity (ECCC), 2001

On the Complexity of Positional Sequencing by Hybridization
Electronic Colloquium on Computational Complexity (ECCC), 2001

Efficient Amplifiers and Bounded Degree Optimization.
Electronic Colloquium on Computational Complexity (ECCC), 2001

1.375-Approximation Algorithm for Sorting by Reversals
Electronic Colloquium on Computational Complexity (ECCC), 2001

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION
Electronic Colloquium on Computational Complexity (ECCC), 2001

Approximating Minimum Unsatisfiability of Linear Equations
Electronic Colloquium on Computational Complexity (ECCC), 2001

Improved approximation algorithms for rectangle tiling and packing.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

An Online Algorithm for the Postman Problem with a Small Penalty.
Proceedings of the Approximation, 2001

2000
Optimal phase conflict removal for layout of dark field alternatingphase shifting masks.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2000

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.
Nord. J. Comput., 2000

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling.
J. Comb. Optim., 2000

Winnowing Sequences from a Database Search.
Journal of Computational Biology, 2000

On-Line Load Balancing for Related Machines.
J. Algorithms, 2000

On-Line Load Balancing for Related Machines
Electronic Colloquium on Computational Complexity (ECCC), 2000

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.
Proceedings of the Algorithm Theory, 2000

Improvements in throughout maximization for real-time scheduling.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Variable length sequencing with two lengths.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem.
SIAM J. Discrete Math., 1999

Speed is More Powerful than Clairvoyance.
Nord. J. Comput., 1999

On Approximation Properties of the Independent Set Problem for Low Degree Graphs.
Theory Comput. Syst., 1999

Post-processing long pairwise alignments.
Bioinformatics, 1999

The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Winnowing sequences from a database search.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

Optimal phase conflict removal for layout of dark field alternating phase shifting masks.
Proceedings of the 1999 International Symposium on Physical Design, 1999

On Some Tighter Inapproximability Results (Extended Abstract).
Proceedings of the Automata, 1999

1998
Alignments without Low-Scoring Regions.
Journal of Computational Biology, 1998

On Some Tighter Inapproximability Results, Further Improvements
Electronic Colloquium on Computational Complexity (ECCC), 1998

On Some Tighter Inapproximability Results
Electronic Colloquium on Computational Complexity (ECCC), 1998

Speed is More Powerful than Claivoyance.
Proceedings of the Algorithm Theory, 1998

Alignments without low-scoring regions.
Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, 1998

Adaptability and the Usefulness of Hints (Extended Abstract).
Proceedings of the Algorithms, 1998

1997
A Nearly Optimal Parallel Algorithm for the Voronoi Diagram of a Convex Polygon.
Theor. Comput. Sci., 1997

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures.
J. Algorithms, 1997

Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems.
Algorithmica, 1997

A Linear-Time Algorithm for the 1-Mismatch Problem.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On-line Load Balancing for Related Machines.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

On-Line Algorithms for Steiner Tree Problems (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Competing against Specialists.
Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

1996
Randomized Robot Navigation Algorithms.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On-line Searching and Navigation.
Proceedings of the Online Algorithms, 1996

Fast Sorting by Reversal.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
On the Approximation Properties of Independent Set Problem in Degree 3 Graphs.
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs.
Proceedings of the Algorithms and Computation, 6th International Symposium, 1995

1994
Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data.
IEEE Trans. Parallel Distrib. Syst., 1994

Reliable distributed diagnosis for multiprocessor systems with random faults.
Networks, 1994

Improved Approximations for the Steiner Tree Problem.
J. Algorithms, 1994

Online Navigation in a Room.
J. Algorithms, 1994

A Nearly Optimal Parallel Algorithm for the Voronoi Diagram of a Convex Polygon.
Proceedings of the Algorithm Theory, 1994

Approximating Maximum Independent Set in Bounded Degree Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Approaching the 5/4-Approximation for Rectilinear Steiner Trees.
Proceedings of the Algorithms, 1994

1993
Cloture Votes: n/4-Resilient Distributed Consensus in t+1 Rounds.
Mathematical Systems Theory, 1993

Fast Consensus in Networks of Bounded Degree.
Distributed Computing, 1993

Quick Atomic Broadcast (Extended Abstract).
Proceedings of the Distributed Algorithms, 7th International Workshop, 1993

Randomized Distributed Agreement Revisited.
Proceedings of the Digest of Papers: FTCS-23, 1993

1992
On the Complexity of Approximating the Independent Set Problem
Inf. Comput., January, 1992

A note on the complexity of reliability in neural networks.
IEEE Trans. Neural Networks, 1992

Optimal Early Stopping in Distributed Consensus (Extended Abstract).
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Improved Approximations for the Steiner Tree Problem.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On-Line Navigation in a Room.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Distributed Consensus in Semi-Synchronous Systems.
Proceedings of the 6th International Parallel Processing Symposium, 1992

1991
Efficient Distributed Consensus with n = (3 + epsilon) t Processors (Extended Abstract).
Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

1990
Weighted Voting for Operation Dependent Management of Replicated Data.
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Fast Consensus in Networks of Bounded Degree (Extended Abstract).
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data.
Proceedings of the Ninth Symposium on Reliable Distributed Systems, 1990

A Competitive 3-Server Algorithm.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Distributed probabilistic fault diagnosis for multiprocessor systems.
Proceedings of the 20th International Symposium on Fault-Tolerant Computing, 1990

1989
On the Complexity of Approximating the Independent Set Problem.
Proceedings of the STACS 89, 1989

Efficient Agreement on Bounded-Degree Networks.
Proceedings of the International Conference on Parallel Processing, 1989

Asymptotically Optimal Distributed Consensus (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Towards Optimal Distributed Consensus (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Investigations of Fault-Tolerant Networks of Computers (Preliminary Version)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987
A Learning Algorithm for a Class of Context-Free Languages (Extended Abstract).
Proceedings of the Methodologies for Intelligent Systems, 1987

Learning One-Counter Languages in Polynomial Time (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1983
Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Deterministic Dynamic Logic of Recursive Programs is Weaker than Dynamic Logic.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
On the Power of Nondeterminism in Dynamic Logic.
Proceedings of the Automata, 1982

1980
A Note on Sweeping Automata.
Proceedings of the Automata, 1980

1978
Relationship Between Density and Deterministic Complexity of NP-Complete Languages.
Proceedings of the Automata, 1978


  Loading...