Relationship Between Density and Deterministic Complexity of NP-Complete Languages. - Piotr Berman (ICALP, 1978)

A Note on Sweeping Automata. - Piotr Berman (ICALP, 1980)

On the Power of Nondeterminism in Dynamic Logic. - Piotr Berman; Joseph Y. Halpern; Jerzy Tiuryn (ICALP, 1982)

Deterministic Dynamic Logic of Recursive Programs is Weaker than Dynamic Logic. - Piotr Berman (FCT, 1983)

Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version) - Piotr Berman; Janos Simon (FOCS, 1983)

Learning One-Counter Languages in Polynomial Time (Extended Abstract) - Piotr Berman; Robert Roos (FOCS, 1987)

A Learning Algorithm for a Class of Context-Free Languages (Extended Abstract). - Piotr Berman; Robert Roos (ISMIS, 1987)

Investigations of Fault-Tolerant Networks of Computers (Preliminary Version) - Piotr Berman; Janos Simon (STOC, 1988)

Towards Optimal Distributed Consensus (Extended Abstract) - Piotr Berman; Juan A. Garay; Kenneth J. Perry (FOCS, 1989)

Asymptotically Optimal Distributed Consensus (Extended Abstract). - Piotr Berman; Juan A. Garay (ICALP, 1989)

Efficient Agreement on Bounded-Degree Networks. - Piotr Berman; Juan A. Garay (ICPP (1), 1989)

Distributed probabilistic fault diagnosis for multiprocessor systems. - Piotr Berman; Andrzej Pelc (FTCS, 1990)

A Competitive 3-Server Algorithm. - Piotr Berman; Howard J. Karloff; Gábor Tardos (SODA, 1990)

Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data. - Mirjana Obradovic; Piotr Berman (SRDS, 1990)

Fast Consensus in Networks of Bounded Degree (Extended Abstract). - Piotr Berman; Juan A. Garay (WDAG, 1990)

Weighted Voting for Operation Dependent Management of Replicated Data. - Mirjana Obradovic; Piotr Berman (WDAG, 1990)

Efficient Distributed Consensus with n = (3 + epsilon) t Processors (Extended Abstract). - Piotr Berman; Juan A. Garay (WDAG, 1991)

Distributed Consensus in Semi-Synchronous Systems. - Piotr Berman; Anupam A. Bharali (IPPS, 1992)

On-Line Navigation in a Room. - Eldad Bar-Eli; Piotr Berman; Amos Fiat; Peiyuan Yan (SODA, 1992)

Optimal Early Stopping in Distributed Consensus (Extended Abstract). - Piotr Berman; Juan A. Garay; Kenneth J. Perry (WDAG, 1992)

A note on the complexity of reliability in neural networks. - Piotr Berman; Ian Parberry; Georg Schnitger (IEEE Trans. Neural Networks, 1992)

On the Complexity of Approximating the Independent Set Problem - Piotr Berman; Georg Schnitger (Inf. Comput., 1992)

Randomized Distributed Agreement Revisited. - Piotr Berman; Juan A. Garay (FTCS, 1993)

Quick Atomic Broadcast (Extended Abstract). - Piotr Berman; Anupam A. Bharali (WDAG, 1993)

Fast Consensus in Networks of Bounded Degree. - Piotr Berman; Juan A. Garay (Distributed Comput., 1993)

Cloture Votes: n/4-Resilient Distributed Consensus in t+1 Rounds. - Piotr Berman; Juan A. Garay (Math. Syst. Theory, 1993)

Approaching the 5/4-Approximation for Rectilinear Steiner Trees. - Piotr Berman; Ulrich Fößmeier; Marek Karpinski; Michael Kaufmann 001; Alexander Zelikovsky (ESA, 1994)

Approximating Maximum Independent Set in Bounded Degree Graphs. - Piotr Berman; Martin Fürer (SODA, 1994)

Online Navigation in a Room. - Eldad Bar-Eli; Piotr Berman; Amos Fiat; Peiyuan Yan (J. Algorithms, 1994)

Improved Approximations for the Steiner Tree Problem. - Piotr Berman; Viswanathan Ramaiyer (J. Algorithms, 1994)

Reliable distributed diagnosis for multiprocessor systems with random faults. - Piotr Berman; Andrzej Pelc (Networks, 1994)

Voting as the Optimal Static Pessimistic Scheme for Managing Replicated Data. - Mirjana Spasojevic; Piotr Berman (IEEE Trans. Parallel Distributed Syst., 1994)

Constant Ratio Approximations of the Weighted Feedback Vertex Set Problem for Undirected Graphs. - Vineet Bafna; Piotr Berman; Toshihiro Fujito (ISAAC, 1995)

On the Approximation Properties of Independent Set Problem in Degree 3 Graphs. - Piotr Berman; Toshihiro Fujito (WADS, 1995)

Fast Sorting by Reversal. - Piotr Berman; Sridhar Hannenhalli (CPM, 1996)

On-line Searching and Navigation. - Piotr Berman (Online Algorithms, 1996)

Randomized Robot Navigation Algorithms. - Piotr Berman; Avrim Blum; Amos Fiat; Howard J. Karloff; Adi Rosén; Michael E. Saks (SODA, 1996)

Competing against Specialists. - Piotr Berman; Juan A. Garay (PODC, 1997)

On-Line Algorithms for Steiner Tree Problems (Extended Abstract). - Piotr Berman; Chris Coulston (STOC, 1997)

A Linear-Time Algorithm for the 1-Mismatch Problem. - Nikola Stojanovic; Piotr Berman; Deborah Gumucio; Ross C. Hardison; Webb Miller (WADS, 1997)

Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems. - Piotr Berman; Bhaskar DasGupta (Algorithmica, 1997)

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures. - Piotr Berman; Krzysztof Diks; Andrzej Pelc (J. Algorithms, 1997)

A Nearly Optimal Parallel Algorithm for the Voronoi Diagram of a Convex Polygon. - Piotr Berman; Andrzej Lingas (Theor. Comput. Sci., 1997)

Adaptability and the Usefulness of Hints (Extended Abstract). - Piotr Berman; Juan A. Garay (ESA, 1998)

Speed is More Powerful than Claivoyance. - Piotr Berman; Chris Coulston (SWAT, 1998)

On Some Tighter Inapproximability Results - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

On Some Tighter Inapproximability Results, Further Improvements - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

Alignments without Low-Scoring Regions. - Zheng Zhang 004; Piotr Berman; Webb Miller (J. Comput. Biol., 1998)

On Some Tighter Inapproximability Results (Extended Abstract). - Piotr Berman; Marek Karpinski (ICALP, 1999)

Optimal phase conflict removal for layout of dark field alternating phase shifting masks. - Piotr Berman; Andrew B. Kahng; Devendra Vidhani; Huijuan Wang; Alexander Zelikovsky (ISPD, 1999)

The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout. - Piotr Berman; Andrew B. Kahng; Devendra Vidhani; Alexander Zelikovsky (WADS, 1999)

Post-processing long pairwise alignments. - Zheng Zhang 004; Piotr Berman; Thomas Wiehe; Webb Miller (Bioinform., 1999)

On Approximation Properties of the Independent Set Problem for Low Degree Graphs. - Piotr Berman; Toshihiro Fujito (Theory Comput. Syst., 1999)

Speed is More Powerful than Clairvoyance. - Piotr Berman; Chris Coulston (Nord. J. Comput., 1999)

A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. - Vineet Bafna; Piotr Berman; Toshihiro Fujito (SIAM J. Discret. Math., 1999)

Variable length sequencing with two lengths. - Piotr Berman; Junichiro Fukuyama (APPROX, 2000)

Improvements in throughout maximization for real-time scheduling. - Piotr Berman; Bhaskar DasGupta (STOC, 2000)

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs. - Piotr Berman (SWAT, 2000)

On-Line Load Balancing for Related Machines - Piotr Berman; Moses Charikar; Marek Karpinski (Electron. Colloquium Comput. Complex., 2000)

Winnowing Sequences from a Database Search. - Piotr Berman; Zheng Zhang 004; Yuri I. Wolf; Eugene V. Koonin; Webb Miller (J. Comput. Biol., 2000)

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling. - Piotr Berman; Bhaskar DasGupta (J. Comb. Optim., 2000)

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

Optimal phase conflict removal for layout of dark field alternatingphase shifting masks. - Piotr Berman; Andrew B. Kahng; Devendra Vidhani; Huijuan Wang; Alexander Zelikovsky (IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2000)

An Online Algorithm for the Postman Problem with a Small Penalty. - Piotr Berman; Junichiro Fukuyama (RANDOM-APPROX, 2001)

Improved approximation algorithms for rectangle tiling and packing. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001; Suneeta Ramaswami (SODA, 2001)

Approximating Minimum Unsatisfiability of Linear Equations - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

1.375-Approximation Algorithm for Sorting by Reversals - Piotr Berman; Sridhar Hannenhalli; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Efficient Amplifiers and Bounded Degree Optimization. - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

On the Complexity of Positional Sequencing by Hybridization - Piotr Berman; Amir Ben-Dor; Itsik Pe'er; Roded Sharan; Ron Shamir (Electron. Colloquium Comput. Complex., 2001)

Improved Approximations for General Minimum Cost Scheduling - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001; Suneeta Ramaswami (J. Algorithms, 2001)

Slice and dice: a simple, improved approximate tiling recipe. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001 (SODA, 2002)

Simple approximation algorithm for nonoverlapping local alignments. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001 (SODA, 2002)

Approximating Huffman Codes in Parallel - Piotr Berman; Marek Karpinski; Yakov Nekrich (Electron. Colloquium Comput. Complex., 2002)

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. - Piotr Berman; Marek Karpinski; Lawrence L. Larmore; Wojciech Plandowski; Wojciech Rytter (J. Comput. Syst. Sci., 2002)

Exact Size of Binary Space Partitionings and Improved Rectangle Tiling Algorithms. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001 (SIAM J. Discret. Math., 2002)

Optimizing misdirection. - Piotr Berman; Piotr Krysta (SODA, 2003)

Aligning two fragmented sequences. - Vamsi Veeramachaneni; Piotr Berman; Webb Miller (Discret. Appl. Math., 2003)

Improved Approximation Lower Bounds on Small Occurrence Optimization - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2003)

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT - Piotr Berman; Marek Karpinski; Alex D. Scott (Electron. Colloquium Comput. Complex., 2003)

Approximation Hardness of Short Symmetric Instances of MAX-3SAT. - Piotr Berman; Marek Karpinski; Alex D. Scott (Electron. Colloquium Comput. Complex., 2003)

Approximability of Hypergraph Minimum Bisection. - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2003)

Approximation algorithms for MAX-MIN tiling. - Piotr Berman; Bhaskar DasGupta; S. Muthukrishnan 001 (J. Algorithms, 2003)

The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices. - Piotr Berman; Bhaskar DasGupta; Dhruv Mubayi; Robert H. Sloan; György Turán; Yi Zhang 002 (CPM, 2004)

Power efficient monitoring management in sensor networks. - Piotr Berman; Gruia Calinescu; C. Shah; Alexander Zelikovsky (WCNC, 2004)

Computational Complexity of Some Restricted Instances of 3SAT - Piotr Berman; Marek Karpinski; Alexander D. Scott (Electron. Colloquium Comput. Complex., 2004)

Fast Optimal Genome Tiling with Applications to Microarray Design and Homology Search. - Piotr Berman; Paul Bertone; Bhaskar DasGupta; Mark Gerstein; Ming-Yang Kao; Michael Snyder 001 (J. Comput. Biol., 2004)

Optimizing sensor movement planning for energy efficiency. - Guiling Wang 001; Mary Jane Irwin; Piotr Berman; Haoying Fu; Thomas F. La Porta (ISLPED, 2005)

On the Vehicle Routing Problem. - Piotr Berman; Surajit K. Das (WADS, 2005)

8/7-Approximation Algorithm for (1,2)-TSP - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2005)

Tight approximability results for test set problems in bioinformatics. - Piotr Berman; Bhaskar DasGupta; Ming-Yang Kao (J. Comput. Syst. Sci., 2005)

Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees. - Piotr Berman; Martin Fürer; Alexander Zelikovsky (CSR, 2006)

8/7-approximation algorithm for (1, 2)-TSP. - Piotr Berman; Marek Karpinski (SODA, 2006)

Controlling Size When Aligning Multiple Genomic Sequences with Duplications. - Minmei Hou; Piotr Berman; Louxin Zhang; Webb Miller (WABI, 2006)

A Linear-Time Algorithm for Studying Genetic Variation. - Nikola Stojanovic; Piotr Berman (WABI, 2006)

Packing to angles and sectors. - Piotr Berman; Jieun K. Jeong; Shiva Prasad Kasiviswanathan; Bhuvan Urgaonkar (Electron. Colloquium Comput. Complex., 2006)

Bringing Folding Pathways into Strand Pairing Prediction. - Jieun K. Jeong; Piotr Berman; Teresa M. Przytycka (WABI, 2007)

Faster Approximation of Distances in Graphs. - Piotr Berman; Shiva Prasad Kasiviswanathan (WADS, 2007)

Foreword. - Piotr Berman; Bhaskar DasGupta; Jie Liang 002 (Algorithmica, 2007)

HomologMiner: looking for homologous genomic groups in whole genomes. - Minmei Hou; Piotr Berman; Chih-Hao Hsu; Robert S. Harris (Bioinform., 2007)

The inverse protein folding problem on 2D and 3D lattices. - Piotr Berman; Bhaskar DasGupta; Dhruv Mubayi; Robert H. Sloan; György Turán; Yi Zhang 002 (Discret. Appl. Math., 2007)

Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. - Piotr Berman; Bhaskar DasGupta; Eduardo D. Sontag (Discret. Appl. Math., 2007)

Computational complexity of some restricted instances of 3-SAT. - Piotr Berman; Marek Karpinski; Alexander D. Scott (Discret. Appl. Math., 2007)

Approximating Transitive Reductions for Directed Networks. - Piotr Berman; Bhaskar DasGupta; Marek Karpinski (Electron. Colloquium Comput. Complex., 2007)

On constructing an optimal consensus clustering from multiple clusterings. - Piotr Berman; Bhaskar DasGupta; Ming-Yang Kao; Jie Wang 002 (Inf. Process. Lett., 2007)

Optimal trade-off for Merkle tree traversal. - Piotr Berman; Marek Karpinski; Yakov Nekrich (Theor. Comput. Sci., 2007)

Bidding Protocols for Deploying Mobile Sensors. - Guiling Wang 001; Guohong Cao; Piotr Berman; Thomas F. La Porta (IEEE Trans. Mob. Comput., 2007)

Fast Alignments of Metabolic Networks. - Qiong Cheng; Piotr Berman; Robert W. Harrison; Alexander Zelikovsky (BIBM, 2008)

HCV Quasispecies Assembly Using Network Flows. - Kelly Westbrooks; Irina Astrovskaya; David S. Campo; Yuri Khudyakov; Piotr Berman; Alexander Zelikovsky (ISBRA, 2008)

On cycles in the transcription network of Saccharomyces cerevisiae. - Jieun K. Jeong; Piotr Berman (BMC Syst. Biol., 2008)

Approximating Transitivity in Directed Networks - Piotr Berman; Bhaskar DasGupta; Marek Karpinski (CoRR, 2008)

A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (CoRR, 2008)

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 2008)

Improving Strand Pairing Prediction through Exploring Folding Cooperativity. - Jieun K. Jeong; Piotr Berman; Teresa M. Przytycka (IEEE ACM Trans. Comput. Biol. Bioinform., 2008)

Approximating the online set multicover problems via randomized winnowing. - Piotr Berman; Bhaskar DasGupta (Theor. Comput. Sci., 2008)

Aligning Two Genomic Sequences That Contain Duplications. - Minmei Hou; Cathy Riemer; Piotr Berman; Ross C. Hardison; Webb Miller (RECOMB-CG, 2009)

1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (WADS, 2009)

Consistent Sets of Secondary Structures in Proteins. - Piotr Berman; Jieun K. Jeong (Algorithmica, 2009)

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications - Piotr Berman; Marek Karpinski; Andrzej Lingas (CoRR, 2009)

On approximating four covering and packing problems. - Mary V. Ashley; Tanya Y. Berger-Wolf; Piotr Berman; Wanpracha Art Chaovalitwongse; Bhaskar DasGupta; Ming-Yang Kao (J. Comput. Syst. Sci., 2009)

Finding Sparser Directed Spanners. - Piotr Berman; Sofya Raskhodnikova; Ge Ruan (FSTTCS, 2010)

Efficient Alignments of Metabolic Networks with Bounded Treewidth. - Qiong Cheng; Piotr Berman; Robert W. Harrison; Alexander Zelikovsky (ICDM Workshops, 2010)

A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (ISAAC (1), 2010)

Successes and Failures of Elegant Algorithms in Computational Biology. - Piotr Berman (ISBRA, 2010)

Steiner Transitive-Closure Spanners of d-Dimensional Posets - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (CoRR, 2010)

O(1)-Approximations for Maximum Movement Problems. - Piotr Berman; Erik D. Demaine; Morteza Zadimoghaddam (APPROX-RANDOM, 2011)

Improved Approximation for the Directed Spanner Problem. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (ICALP (1), 2011)

HybridStore: A Cost-Efficient, High-Performance Storage System Combining SSDs and HDDs. - Youngjae Kim 001; Aayush Gupta; Bhuvan Urgaonkar; Piotr Berman; Anand Sivasubramaniam (MASCOTS, 2011)

On Systemic Stability of Banking Networks - Piotr Berman; Bhaskar DasGupta; Lakshmi Kaligounder; Marek Karpinski (CoRR, 2011)

Optimizing sensor movement planning for energy efficiency. - Guiling Wang 001; Mary Jane Irwin; Haoying Fu; Piotr Berman; Wensheng Zhang 001; Tom La Porta (ACM Trans. Sens. Networks, 2011)

Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. - Piotr Berman; Grigory Yaroslavtsev (APPROX-RANDOM, 2012)

Improving the performance of k-means clustering through computation skipping and data locality optimizations. - Orhan Kislal; Piotr Berman; Mahmut T. Kandemir (Conf. Computing Frontiers, 2012)

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. - Piotr Berman; Marek Karpinski; Andrzej Lingas (Algorithmica, 2012)

Approximation algorithms for spanner problems and Directed Steiner Forest. - Piotr Berman; Arnab Bhattacharyya 001; Konstantin Makarychev; Sofya Raskhodnikova; Grigory Yaroslavtsev (Inf. Comput., 2013)

Lp-testing. - Piotr Berman; Sofya Raskhodnikova; Grigory Yaroslavtsev (STOC, 2014)

On the Computational Complexity of Measuring Global Stability of Banking Networks. - Piotr Berman; Bhaskar DasGupta; Lakshmi Kaligounder; Marek Karpinski (Algorithmica, 2014)

Steiner transitive-closure spanners of low-dimensional posets. - Piotr Berman; Arnab Bhattacharyya 001; Elena Grigorescu; Sofya Raskhodnikova; David P. Woodruff; Grigory Yaroslavtsev (Comb., 2014)

Approximation Algorithms for Min-Max Generalization Problems. - Piotr Berman; Sofya Raskhodnikova (ACM Trans. Algorithms, 2014)

HybridPlan: a capacity planning technique for projecting storage requirements in hybrid storage systems. - Youngjae Kim 001; Aayush Gupta; Bhuvan Urgaonkar; Piotr Berman; Anand Sivasubramaniam (J. Supercomput., 2014)

The Distributed Selection Problem and the AKS Sorting Network. - Piotr Berman; Junichiro Fukuyama (CoRR, 2015)

Constant-Time Testing and Learning of Image Properties. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (CoRR, 2015)

The Power and Limitations of Uniform Samples in Testing Properties of Figures. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (Algorithmica, 2019)

Testing convexity of figures under the uniform distribution. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (Random Struct. Algorithms, 2019)

Tolerant Testers of Image Properties. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova (ACM Trans. Algorithms, 2022)

Testing Connectedness of Images. - Piotr Berman; Meiram Murzabulatov; Sofya Raskhodnikova; Dragos-Florian Ristache (Algorithmica, 2024)