Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link
11	Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Denil Sharipov	Polynomial formulations as a barrier for reduction-based hardness proofs.	SODA	2023	DBLP DOI BibTeX RDF
11	Huong Luu, Marek Chrobak	Better Hardness Results for the Minimum Spanning Tree Congestion Problem.	WALCOM	2023	DBLP DOI BibTeX RDF
11	A. Mohanapriya, P. Renjith, N. Sadagopan	Roman k-Domination: Hardness, Approximation and Parameterized Results.	WALCOM	2023	DBLP DOI BibTeX RDF
11	Omaimah Al Hosni, Andrew J. Starkey	Can Complexity Measures and Instance Hardness Measures Reflect the Actual Complexity of Microarray Data?	LOD (1)	2023	DBLP DOI BibTeX RDF
11	Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi	Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses.	ITCS	2023	DBLP DOI BibTeX RDF
11	Zvika Brakerski, Ran Canetti, Luowen Qian	On the Computational Hardness Needed for Quantum Cryptography.	ITCS	2023	DBLP DOI BibTeX RDF
11	Giacomo Santona, Tiziano Fapanni, Antonio Fiorentino, Francesco Doglietto, Mauro Serpelloni	Preliminary Study on a 3D Printed Sensorized Probe to Characterize Pituitary Adenoma Hardness.	MetroInd4.0&IoT	2023	DBLP DOI BibTeX RDF
11	Takuya Sasaki, Daiki Hagimori, Monica Perusquía-Hernández, Naoya Isoyama, Hideaki Uchiyama, Kiyoshi Kiyokawa, Yoshihiro Kuroda	A Two-layer Haptic Device for Presenting a Wide Range of Softness and Hardness Using a Pneumatic Balloon and a Mechanical Piston.	RO-MAN	2023	DBLP DOI BibTeX RDF
11	Michael Roumeliotis, Katerina Mania	A Lightweight Haptic Feedback Glove Employing Normal Indentation, Lateral Skin Stretch and both Softness and Hardness Rendering.	ISMAR-Adjunct	2023	DBLP DOI BibTeX RDF
11	Haoxin Liu, Pu Zhao 0004, Si Qin, Yong Shi 0012, Mirror Xu, Qingwei Lin, Dongmei Zhang 0001	HAPENS: Hardness-Personalized Negative Sampling for Implicit Collaborative Filtering.	WWW (Companion Volume)	2023	DBLP DOI BibTeX RDF
11	Jedrzej Potoniec	Is the Proof Length a Good Indicator of Hardness for Reason-able Embeddings?	NeSy	2023	DBLP BibTeX RDF
11	Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang	Improved Hardness of Approximating k-Clique under ETH.	FOCS	2023	DBLP DOI BibTeX RDF
11	Benny Applebaum, Oded Nir	Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography.	FOCS	2023	DBLP DOI BibTeX RDF
11	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	FOCS	2023	DBLP DOI BibTeX RDF
11	Divesh Aggarwal, Rajendra Kumar 0002	Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!	FOCS	2023	DBLP DOI BibTeX RDF
11	Suprovat Ghoshal, Euiwoong Lee	On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.	FOCS	2023	DBLP DOI BibTeX RDF
11	Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto	Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.	ICALP	2023	DBLP DOI BibTeX RDF
11	Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans	Improved Hardness Results for the Guided Local Hamiltonian Problem.	ICALP	2023	DBLP DOI BibTeX RDF
11	Akane Tamura, Irwansyah Irwansyah, Sho Otsuka, Seiji Nakagawa	Effects of hardness and dimension of pinna and auricular hematoma on detection threshold of cartilage conduction.	EMBC	2023	DBLP DOI BibTeX RDF
11	Zahraa N. Abdul Hussain, Mohammed Jameel Alsalhy	Optimization of Metal Removal Rate, Surface Roughness, and Hardness Using the Taguchi Method in CNC Turning Machine.	FICTA (2)	2023	DBLP DOI BibTeX RDF
11	Ting Rang Ling, Mohammed Ayoub Juman, Surya Girinatha Nurzaman, Chee Pin Tan	Shape-invariant Indirect Hardness Estimation for a Soft Vacuum-actuated Gripper with an Onboard Depth Camera.	RoboSoft	2023	DBLP DOI BibTeX RDF
11	Xiong Zeng, Zexiang Liu, Zhe Du, Necmiye Ozay, Mario Sznaier	On the Hardness of Learning to Stabilize Linear Systems.	CDC	2023	DBLP DOI BibTeX RDF
11	Junyan Su, Qiulin Lin, Minghua Chen 0001, Haibo Zeng 0001	Minimizing Carbon Footprint for Timely E-Truck Transportation: Hardness and Approximation Algorithm.	CDC	2023	DBLP DOI BibTeX RDF
11	Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, Junchi Yan	HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baseline.	KDD	2023	DBLP DOI BibTeX RDF
11	Md Mahabub Uz Zaman, Liangde Tao, Mark Maldonado, Chang Liu, Ahmed Sunny, Shouhuai Xu, Lin Chen 0009	Optimally Blending Honeypots into Production Networks: Hardness and Algorithms.	SciSec	2023	DBLP DOI BibTeX RDF
11	Shiyuan Deng, Shangqi Lu, Yufei Tao 0001	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms.	PODS	2023	DBLP DOI BibTeX RDF
11	Antoine Dailly, Florent Foucaud, Anni Hakanen	Algorithms and Hardness for Metric Dimension on Digraphs.	WG	2023	DBLP DOI BibTeX RDF
11	Artur Pak, Sultan Nurmukhamedov, Rustem Takhanov, Zhenisbek Assylbekov	Hardness of Learning AES Key (Student Abstract).	AAAI	2023	DBLP DOI BibTeX RDF
11	Markus Hecher	Characterizing Structural Hardness of Logic Programs: What Makes Cycles and Reachability Hard for Treewidth?	AAAI	2023	DBLP DOI BibTeX RDF
11	Xiaomeng Lei, Mahesh Tripunitara	The Hardness of Learning Access Control Policies.	SACMAT	2023	DBLP DOI BibTeX RDF
11	Kameng Nip	On the NP-Hardness of Two Scheduling Problems Under Linear Constraints.	IJTCS-FAW	2023	DBLP DOI BibTeX RDF
11	T.-H. Hubert Chan, Zhihao Gavin Tang, Quan Xue	Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant.	IJTCS-FAW	2023	DBLP DOI BibTeX RDF
11	Stephan Wäldchen	Hardness of Deceptive Certificate Selection.	xAI (3)	2023	DBLP DOI BibTeX RDF
11	Katharina Kreuzer, Tobias Nipkow	Verification of NP-Hardness Reduction Functions for Exact Lattice Problems.	CADE	2023	DBLP DOI BibTeX RDF
11	Yiwen Liu, Senlin Fang, Chengliang Liu 0004, Jingnan Wang, Ke Mai, Yupo Zhang, Zhengkun Yi, Xinyu Wu 0001	Evaluation of Continual Learning Methods for Object Hardness Recognition.	RCAR	2023	DBLP DOI BibTeX RDF
11	Lehilton L. C. Pedrosa, Mauro R. C. da Silva, Rafael C. S. Schouery	Positional Knapsack Problem: NP-hardness and approximation scheme (Brief Announcement).	LAGOS	2023	DBLP DOI BibTeX RDF
11	Jingbang Chen, Yu Gao 0001, Yufan Huang, Richard Peng, Runze Wang	Hardness of Graph-Structured Algebraic and Symbolic Problems.	WADS	2023	DBLP DOI BibTeX RDF
11	Thi-Mai-Anh Bui, Quoc-Trung Bui, Van-Tri Do	A Novel Fitness Function for Automated Software Test Case Generation Based on Nested Constraint Hardness.	GECCO Companion	2023	DBLP DOI BibTeX RDF
11	Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan	SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.	EUROCRYPT (2)	2023	DBLP DOI BibTeX RDF
11	Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa	From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments.	EUROCRYPT (1)	2023	DBLP DOI BibTeX RDF
11	Dipayan Das 0001, Antoine Joux	On the Hardness of the Finite Field Isomorphism Problem.	EUROCRYPT (5)	2023	DBLP DOI BibTeX RDF
11	Shweta Agrawal, Simran Kumari, Anshu Yadav, Shota Yamada 0001	Broadcast, Trace and Revoke with Optimal Parameters from Polynomial Hardness.	EUROCRYPT (3)	2023	DBLP DOI BibTeX RDF
11	Dror Chawin, Ishay Haviv	Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank.	STACS	2023	DBLP DOI BibTeX RDF
11	Suryajith Chillara, Coral Grichener, Amir Shpilka	On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.	STACS	2023	DBLP DOI BibTeX RDF
11	Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora	Hardness of Balanced Mobiles.	IWOCA	2023	DBLP DOI BibTeX RDF
11	Kusum, Arti Pandey	Cosecure Domination: Hardness Results and Algorithms.	IWOCA	2023	DBLP DOI BibTeX RDF
11	Shotaro Sugitani, Ryuichi Nakajima, Takafumi Ito, Jun Furuta, Kazutoshi Kobayashi, Mathieu Louvat, Francois Jacquet, Jean-Christophe Eloy, Olivier Montfort, Lionel Jure, Vincent Huard	Radiation Hardness Evaluations of a Stacked Flip Flop in a 22 nm FD-SOI Process by Heavy-Ion Irradiation.	IOLTS	2023	DBLP DOI BibTeX RDF
11	Aibin Yan, Chao Zhou, Shaojie Wei, Jie Cui 0004, Zhengfeng Huang, Patrick Girard 0001, Xiaoqing Wen	Design of a Novel Latch with Quadruple-Node-Upset Recovery for Harsh Radiation Hardness.	ITC-Asia	2023	DBLP DOI BibTeX RDF
11	Omaimah Al Hosni, Andrew J. Starkey	Investigating the Performance of Data Complexity & Instance Hardness Measures as A Meta-Feature in Overlapping Classes Problem.	ICCBDC	2023	DBLP DOI BibTeX RDF
11	Shinji Kobayashi, Takahiro Sato, Takanori Yamazaki	Relationship Between Tableting Motion and Tablet Hardness in Compression Molding.	ICINCO (2)	2023	DBLP DOI BibTeX RDF
11	Jingfeng Wu, Wennan Zhu, Peter Kairouz, Vladimir Braverman	Private Federated Frequency Estimation: Adapting to the Hardness of the Instance.	NeurIPS	2023	DBLP BibTeX RDF
11	Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang	Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products.	NeurIPS	2023	DBLP BibTeX RDF
11	Wai Ming Tai, Bryon Aragam	Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures.	COLT	2023	DBLP BibTeX RDF
11	Stefan Tiegel	Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems.	COLT	2023	DBLP BibTeX RDF
11	Sihan Liu, Gaurav Mahajan, Daniel Kane 0001, Shachar Lovett, Gellért Weisz, Csaba Szepesvári	Exponential Hardness of Reinforcement Learning with Linear Function Approximation.	COLT	2023	DBLP BibTeX RDF
11	Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou	Multitask Learning via Shared Features: Algorithms and Hardness.	COLT	2023	DBLP BibTeX RDF
11	Okke van Eck, Daan van den Berg	Quantifying Instance Hardness of Protein Folding within the HP-model.	CIBCB	2023	DBLP DOI BibTeX RDF
11	Hu Fu 0001, Jiawei Li, Daogao Liu	Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme.	STOC	2023	DBLP DOI BibTeX RDF
11	Shuichi Hirahara, Nobutaka Shimizu	Hardness Self-Amplification: Simplified, Optimized, and Unified.	STOC	2023	DBLP DOI BibTeX RDF
11	Shuichi Hirahara	Capturing One-Way Functions via NP-Hardness of Meta-Complexity.	STOC	2023	DBLP DOI BibTeX RDF
11	Yizhi Huang, Rahul Ilango, Hanlin Ren	NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.	STOC	2023	DBLP DOI BibTeX RDF
11	Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai	Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness.	STOC	2023	DBLP DOI BibTeX RDF
11	Sangjin Park, Dae Ha Kim, Byung Cheol Song	Fine Gaze Redirection Learning with Gaze Hardness-aware Transformation.	WACV	2023	DBLP DOI BibTeX RDF
11	Lusheng Wang 0001, Binhai Zhu	Algorithms and Hardness for the Longest Common Subsequence of Three Strings and Related Problems.	SPIRE	2023	DBLP DOI BibTeX RDF
11	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant Depth Circuits: Hardness and Algorithms.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
11	Yahli Hecht, Dor Minzer, Muli Safra	NP-Hardness of Almost Coloring Almost 3-Colorable Graphs.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
11	Huck Bennett, Chris Peikert	Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
11	Anupam Gupta 0001, Amit Kumar 0001, Debmalya Panigrahi	Efficient Algorithms and Hardness Results for the Weighted k-Server Problem.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
11	Kanat Alimanov, Zhenisbek Assylbekov	Hardness of Learning AES with Gradient-Based Methods.	CANS	2023	DBLP DOI BibTeX RDF
11	Yanyi Liu, Rafael Pass	One-Way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions.	CRYPTO (2)	2023	DBLP DOI BibTeX RDF
11	Parker Newton, Silas Richelson	A Lower Bound for Proving Hardness of Learning with Rounding with Polynomial Modulus.	CRYPTO (5)	2023	DBLP DOI BibTeX RDF
11	Maxime Bombar, Geoffroy Couteau, Alain Couvreur, Clément Ducros	Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding.	CRYPTO (4)	2023	DBLP DOI BibTeX RDF
11	Robert D. Barish, Tetsuo Shibuya	Hardness of Bounding Influence via Graph Modification.	SOFSEM	2023	DBLP DOI BibTeX RDF
11	Meng-Shiou Tsai, Sun-Yuan Hsieh, Ling-Ju Hung	Hardness and Approximation for the Star β-Hub Routing Cost Problem in $\varDelta _\beta $-Metric Graphs.	COCOON (1)	2023	DBLP DOI BibTeX RDF
11	Hengzhao Ma, Jianzhong Li 0001	The Hardness of Optimization Problems on the Weighted Massively Parallel Computation Model.	COCOON (2)	2023	DBLP DOI BibTeX RDF
11	Venkatesan Guruswami, Rishi Saket	Hardness of Learning Boolean Functions from Label Proportions.	FSTTCS	2023	DBLP DOI BibTeX RDF
11	Yanyi Liu, Rafael Pass	Leakage-Resilient Hardness vs Randomness.	CCC	2023	DBLP DOI BibTeX RDF
11	Dieter van Melkebeek, Nicollas M. Sdroievski	Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols.	CCC	2023	DBLP DOI BibTeX RDF
11	Eshan Chattopadhyay, Jyun-Jie Liao	Hardness Against Linear Branching Programs and More.	CCC	2023	DBLP DOI BibTeX RDF
11	Ilias Diakonikolas, Daniel Kane 0001, Lisheng Ren	Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.	ICML	2023	DBLP BibTeX RDF
11	Dylan J. Foster, Noah Golowich, Sham M. Kakade	Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games.	ICML	2023	DBLP BibTeX RDF
11	Haotian Ye, Xiaoyu Chen, Liwei Wang 0001, Simon Shaolei Du	On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness.	ICML	2023	DBLP BibTeX RDF
11	Benito van der Zander, Markus Bläser, Maciej Liskiewicz	The Hardness of Reasoning about Probabilities and Causality.	IJCAI	2023	DBLP DOI BibTeX RDF
11	Akihito Kobayashi, Takuto Nebashi, Akira Ohta	Relationship between Food Hardness and Frequency Response Using Swept-Sine Technique.	GCCE	2023	DBLP DOI BibTeX RDF
11	Maxime Bombar	Codes Structurés pour la Cryptographie: des Fondations Théoriques de la Sécurité aux Applications. (Structured Codes for Cryptography: from Source of Hardness to Applications).		2023	RDF
11	Yu Wang, Jie Wu, Hanfu He, Shuaishuai Wang	The impact of audio effects processing on the perception of hardness of Bass Drum.	Cogn. Comput. Syst.	2022	DBLP DOI BibTeX RDF
11	Mao Cai, Ning Cheng, Chunzheng Cao, Jianwei Yang, Yunjie Chen	Adaptive Hardness Indicator Softmax for Deep Face Recognition.	Int. J. Pattern Recognit. Artif. Intell.	2022	DBLP DOI BibTeX RDF
11	Antoine Désir, Vineet Goyal, Jiawei Zhang 0006	Technical Note - Capacitated Assortment Optimization: Hardness and Approximation.	Oper. Res.	2022	DBLP DOI BibTeX RDF
11	Martin Bichler, Stefan Waldherr	Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions.	Oper. Res.	2022	DBLP DOI BibTeX RDF
11	Zhifen Zhang, Rui Qin, Geng Li, Zimin Liu, Guangrui Wen, Weifeng He	Online Evaluation of Surface Hardness for Aluminum Alloy in LSP Using Modal Acoustic Emission.	IEEE Trans. Instrum. Meas.	2022	DBLP DOI BibTeX RDF
11	Jingjing Ma, Haitao Jiang, Daming Zhu, Runmin Yang	Algorithms and Hardness for Scaffold Filling to Maximize Increased Duo-Preservations.	IEEE ACM Trans. Comput. Biol. Bioinform.	2022	DBLP DOI BibTeX RDF
11	Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan	Near-Optimal NP-Hardness of Approximating Max k-CSPR.	Theory Comput.	2022	DBLP BibTeX RDF
11	Danupon Nanongkai, Michele Scquizzato	Equivalence classes and conditional hardness in massively parallel computations.	Distributed Comput.	2022	DBLP DOI BibTeX RDF
11	Sushmita Gupta, Saket Saurabh 0001, Meirav Zehavi	On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization).	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
11	Julian Dörfler, Marc Roth, Johannes Schmitt 0002, Philip Wellnitz	Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness.	Algorithmica	2022	DBLP DOI BibTeX RDF
11	Shaohua Li 0005, Marcin Pilipczuk	Hardness of Metric Dimension in Graphs of Constant Treewidth.	Algorithmica	2022	DBLP DOI BibTeX RDF
11	Chenglin Fan, Benjamin Raichel, Gregory Van Buskirk	Metric Violation Distance: Hardness and Approximation.	Algorithmica	2022	DBLP DOI BibTeX RDF
11	Hao-Ping Yeh, Wei Lu, Li-Hsuan Chen, Ling-Ju Hung, Ralf Klasing, Sun-Yuan Hsieh	Hardness and approximation for the star p-Hub Routing Cost Problem in metric graphs.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Gábor Kondor	NP-hardness of m-dimensional weighted matching problems.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Abolfazl Poureidi	Algorithm and hardness results in double Roman domination of graphs.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF